Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations SkipVought on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
convert Decimal to Fraction
- Thread starter Timinator
- Start date
MichaelRed
Programmer
Hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm,
Depends on your definition of easy - and the 'accuracy' desired or necessary in the fraction. It HAS been discussed on Tek-Tips (either Ms. Access or VB) 'recently'. Try a search on "fraction".
MichaelRed
m.red@att.net
There is never time to do it right but there is always time to do it over
Depends on your definition of easy - and the 'accuracy' desired or necessary in the fraction. It HAS been discussed on Tek-Tips (either Ms. Access or VB) 'recently'. Try a search on "fraction".
MichaelRed
m.red@att.net
There is never time to do it right but there is always time to do it over
JohnYingling
Programmer
Extract the number of digits to the left of the decimal point. Then
if Len(strDecimals) > 0 then
strFraction = strDecimals & "/" & Cstr(10 ^ (Len(strDecimals))
End if
' .1 = 1/10
' .55 = 55 55/100
' .333 = 333/1000
...now reducing it to lowest terms is a horse of a different color. Compare Code (Text)
Generate Sort in VB or VBScript
if Len(strDecimals) > 0 then
strFraction = strDecimals & "/" & Cstr(10 ^ (Len(strDecimals))
End if
' .1 = 1/10
' .55 = 55 55/100
' .333 = 333/1000
...now reducing it to lowest terms is a horse of a different color. Compare Code (Text)
Generate Sort in VB or VBScript
This isn't necessarily the most elegant method of finding lowest terms, but it works fast enough up to about 5 or 6 decimal places.
[tt]
Public Function Fraction(dblSource As Double) As String
Dim lp As Long
Dim strNumber As String
Dim strDecimals As String
' Slight rework of JohnYingling's example to get
' numerator and denominator as numerics rather than
' string
strNumber = CStr(dblSource)
strDecimals = Right(strNumber, Len(strNumber) - InStr(strNumber, "."
)
If Len(strDecimals) > 0 Then
lngN = CLng(strDecimals)
lngD = 10 ^ (Len(strDecimals))
End If
' Given a numerator and denominator, reduce to
' lowest terms by checking for common factors, stating with the highest
For lp = lngN To 2 Step -1 ' No need to check 1
If lngN Mod lp = 0 Then
If lngD Mod lp = 0 Then
lngN = lngN / lp
lngD = lngD / lp
lp = lngN ' reduce search space
End If
End If
Next
Fraction = Fix(dblSource) & " " & lngN & "/" & lngD
End Function
[tt]
Public Function Fraction(dblSource As Double) As String
Dim lp As Long
Dim strNumber As String
Dim strDecimals As String
' Slight rework of JohnYingling's example to get
' numerator and denominator as numerics rather than
' string
strNumber = CStr(dblSource)
strDecimals = Right(strNumber, Len(strNumber) - InStr(strNumber, "."
)If Len(strDecimals) > 0 Then
lngN = CLng(strDecimals)
lngD = 10 ^ (Len(strDecimals))
End If
' Given a numerator and denominator, reduce to
' lowest terms by checking for common factors, stating with the highest
For lp = lngN To 2 Step -1 ' No need to check 1
If lngN Mod lp = 0 Then
If lngD Mod lp = 0 Then
lngN = lngN / lp
lngD = lngD / lp
lp = lngN ' reduce search space
End If
End If
Next
Fraction = Fix(dblSource) & " " & lngN & "/" & lngD
End Function
WilMead
IS-IT--Management
Factoring is easy once you remember a few tricks.
Prime numbers makes the problem so much more fun.
When looking for factors, start (or stop) at the square root of the number (nearest whole number is fine). That is the point where you factor pairs begin to repeat.
HCM = Product of non-shaired factors.
LCD = Product of prime factors counting shaired pairs once.
60 = 5*3*2*2
--
90 = 5*3*2*3
Dropping 5*3*2 (30) we get HCM = 60/90 = 2/3.
For LCD we get (5*3*3*2*2) = 180.
All you need now is a prime number object that does Next, Previous, and Factors (Get/Let).
The factor list should be constructed so that the Prime number is the key, and the power is the primes exponent.
In the Combination process for LCM, Create a new factor list containing all keys in the original list, but only the highest exponents. For HCM the new exponents are equal to the difference of the exponents. Use ABS. Using a collection object for the list lets you use the add error as a trap for the special operations of the method.
Of course there is that nasty oversight that makes the collections key non-readable. You'll need an object just to store the factor.
Good luck.
Wil Mead
wmead@optonline.net
Prime numbers makes the problem so much more fun.
When looking for factors, start (or stop) at the square root of the number (nearest whole number is fine). That is the point where you factor pairs begin to repeat.
HCM = Product of non-shaired factors.
LCD = Product of prime factors counting shaired pairs once.
60 = 5*3*2*2
--
90 = 5*3*2*3
Dropping 5*3*2 (30) we get HCM = 60/90 = 2/3.
For LCD we get (5*3*3*2*2) = 180.
All you need now is a prime number object that does Next, Previous, and Factors (Get/Let).
The factor list should be constructed so that the Prime number is the key, and the power is the primes exponent.
In the Combination process for LCM, Create a new factor list containing all keys in the original list, but only the highest exponents. For HCM the new exponents are equal to the difference of the exponents. Use ABS. Using a collection object for the list lets you use the add error as a trap for the special operations of the method.
Of course there is that nasty oversight that makes the collections key non-readable. You'll need an object just to store the factor.
Good luck.
Wil Mead
wmead@optonline.net
Here is what I wrote. It converts a double to string fraction of the specified denominator and rounds up, down or to the next nearest value. It calls a custom rounding procedure, shown below.
Hope this helps.
Code:
Public Function DecimalToFraction(ByVal dNumber As Double, ByVal iDenominator As Integer, sMethod As String) As String
Dim dRes As Double
Dim dPrec As Double
Dim iIn As Long, iParts As Integer
dPrec = 1 / iDenominator 'decimal precision
dRes = 0: iIn = 0: iParts = 0
dRes = Round(dNumber, dPrec, sMethod)
iIn = Int(dRes)
iParts = CInt((dRes - iIn) * iDenominator)
If iParts = iDenominator Then
DecimalToFraction = CStr(iIn + 1)
ElseIf iParts > 0 Then
Do While (iParts Mod 2) = 0 And (iDenominator Mod 2) = 0
iParts = iParts / 2
iDenominator = iDenominator / 2
Loop
If iIn > 0 Then
DecimalToFraction = CStr(iIn) & " " & CStr(iParts) & "/" & CStr(iDenominator)
Else
DecimalToFraction = CStr(iParts) & "/" & CStr(iDenominator)
End If
Else 'parts=0
DecimalToFraction = CStr(iIn)
End If
End Function
Public Function Round(dNumber As Double, dIncrement As Double, sMethod As String) As Double
If sMethod Like "U" Then
Round = CLng((dNumber + dIncrement / 2) / dIncrement) * dIncrement
ElseIf sMethod Like "D" Then
Round = CLng((dNumber - dIncrement / 2) / dIncrement) * dIncrement
Else 'assume nearest
Round = CLng(dNumber / dIncrement) * dIncrement
End If
End FunctionJohnYingling
Programmer
Strongm,
If no decimal point then the entire string becomes decimals because Instr returns 0.
Change this
strDecimals = Right(strNumber, Len(strNumber) - InStr(strNumber, ".")
If Len(strDecimals) > 0 Then
To
Dim lngInstr As Long
lngInstr = InStr(strNumber, "."
if lngInstr > 0 then
strDecimals = Mid$(strNumber, lngInStr + 1)
If Len(strDecimals) > 0 Then
Compare Code (Text)
Generate Sort in VB or VBScript
If no decimal point then the entire string becomes decimals because Instr returns 0.
Change this
strDecimals = Right(strNumber, Len(strNumber) - InStr(strNumber, "."
)If Len(strDecimals) > 0 Then
To
Dim lngInstr As Long
lngInstr = InStr(strNumber, "."
if lngInstr > 0 then
strDecimals = Mid$(strNumber, lngInStr + 1)
If Len(strDecimals) > 0 Then
Compare Code (Text)
Generate Sort in VB or VBScript
It's a fair cop - but then I haven't got any error checking either...<grin>
Mind you, I think my preference would be just to surround the whole thing with a:
' variable declarations
If dblSource - Fix(dblSource) = 0 Then 'or similar test. Lots of ways of doing this
Fraction = CStr(dblSource)
Else
' All the original code
Endif
Mind you, I think my preference would be just to surround the whole thing with a:
' variable declarations
If dblSource - Fix(dblSource) = 0 Then 'or similar test. Lots of ways of doing this
Fraction = CStr(dblSource)
Else
' All the original code
Endif
MichaelRed
Programmer
Code:
Public Function basDec2Fraction(ValIn As Double) As String
'Michael Red 2/6/2002. Tek-Tips Thread "thread222-206890"'
'convert Decimal to Fraction
Dim strDec As String
Dim ValParts() As String
Dim ReducedFract As String
Dim strVal As String
Dim lngNumer As Long
Dim lngDenom As Long
Dim ModOp As Long
Dim Reduce As Boolean
strDec = CStr(ValIn)
ValParts = Split(strDec, ".")
If (UBound(ValParts) <> 1) Then
'Uh Oh! No Decimal to convert.
basDec2Fraction = ValParts(0)
Exit Function
End If
lngNumer = CLng(ValParts(1))
lngDenom = CLng(10 ^ Len(ValParts(1)))
If Len(ValParts(1)) > 0 Then
ModOp = lngNumer / 2
Do While ModOp >= 2
If ((lngNumer Mod ModOp = 0) And (lngDenom Mod ModOp = 0)) Then
lngNumer = lngNumer / ModOp
lngDenom = lngDenom / ModOp
ModOp = lngNumer / 2
Else
ModOp = ModOp - 1
End If
Loop
strVal = ValParts(0) & " and " & Trim(CStr(lngNumer)) & "/" & Trim(CStr(lngDenom))
End If
basDec2Fraction = strVal
End FunctionIt does -of course- depend on what the specification requires, as well as the 'resources'. Will has some 'interesting' thoughts, but even if / when they are reduced to usable code, I am not at all sure there will be any real improvement to the execution process over the "brute force" approaches discussed by others (incl self).
What COULD be interesting (assumimg both are 'bug free') would be to compare the accuracy and execution time for the procedures. For Instance, I am sure that 'my' approach will reduce the fraction somewhat. I am NOT sure it always actually finds the lowest denominator.
MichaelRed
m.red@att.net
There is never time to do it right but there is always time to do it over
Hey MichaelRed, couple of comments:
that's just an exact rewrite of my algorithm, merely converting the For...Next into a Do...While. Granted, you make one minor change with the division by 2 to try and reduce the brute force search space - but this unfortunately means that some decimals are not reduced properly (eg n.04, n.25, n.5) because it misses the cases where the numerator is itself a factor of the denominator.
Oh, and you combine the If statements. If time were to be an issue this might be a mistake, as VB doesn't shortcircuit compound Ifs; all expressions in the statement are evaluated, even if the first one fails (on that note, guess what? VB.NET introduces shortcircuiting...).
that's just an exact rewrite of my algorithm, merely converting the For...Next into a Do...While. Granted, you make one minor change with the division by 2 to try and reduce the brute force search space - but this unfortunately means that some decimals are not reduced properly (eg n.04, n.25, n.5) because it misses the cases where the numerator is itself a factor of the denominator.
Oh, and you combine the If statements. If time were to be an issue this might be a mistake, as VB doesn't shortcircuit compound Ifs; all expressions in the statement are evaluated, even if the first one fails (on that note, guess what? VB.NET introduces shortcircuiting...).
MichaelRed
Programmer
Not to argumentative ... but "Exact rewrite ... " <> " ... couple of changes ...", and I think the reduces search is possible important and does NOT skip any viable reduction. Since no number can be a multiple of a value > 1/2 of itself, the reduction in the moduls value immediatly after a 'sucessful' reduction is meremly taking advantage of that. All other reductions in the moduls are by simple decrement.
My point was NOT to claim originality, but to furnish an incremental improvement in the thread postings and to hopefully spur others to greater efforts. While I did use your code as a starting point for the reduction, I had long ago done the upper part, and had considered the reduction scheme as well, but never implemented it.
MichaelRed
m.red@att.net
There is never time to do it right but there is always time to do it over
My point was NOT to claim originality, but to furnish an incremental improvement in the thread postings and to hopefully spur others to greater efforts. While I did use your code as a starting point for the reduction, I had long ago done the upper part, and had considered the reduction scheme as well, but never implemented it.
MichaelRed
m.red@att.net
There is never time to do it right but there is always time to do it over
what could be the purpose of converting decimals to fractions in a base 10 numerical system using limited binary numerical representations in a computer?
we could represent them as strings and concoct all sorts of fancy algorithms to make sure that there were no rounding errors between the base systems. how could we be sure that they weren't further reducible? (e.g. 6/10). that is trivial to prove in some cases but it is not always non-trivial. a previous respondent noted we come down to factoring, and with that goes testing the primality of numbers. if you have a foolproof method for testing the primality of arbitrarily large numbers, my guess is that somebody would buy that for a darn dollar.
what about irrational numbers? is the result 22/7 = Pi accurate enough? this issue was also mentioned.
i was involved in a project that required a large number of calculations in which cumulative binary rounding errors were unacceptably large. i split the numbers into numerators and denominators, simplified when it was easy, or when there was an impending overflow, and put out an array of decimals that was almost exactly correct. i never considered converting that resuslt to fractions.
john
we could represent them as strings and concoct all sorts of fancy algorithms to make sure that there were no rounding errors between the base systems. how could we be sure that they weren't further reducible? (e.g. 6/10). that is trivial to prove in some cases but it is not always non-trivial. a previous respondent noted we come down to factoring, and with that goes testing the primality of numbers. if you have a foolproof method for testing the primality of arbitrarily large numbers, my guess is that somebody would buy that for a darn dollar.
what about irrational numbers? is the result 22/7 = Pi accurate enough? this issue was also mentioned.
i was involved in a project that required a large number of calculations in which cumulative binary rounding errors were unacceptably large. i split the numbers into numerators and denominators, simplified when it was easy, or when there was an impending overflow, and put out an array of decimals that was almost exactly correct. i never considered converting that resuslt to fractions.
john
<ahem>
>I did use your code as a starting point
Starting point? It's the exact same algorithm (barring the one issue I discuss below). Which would be fine if you'd credited it at all, as opposed to putting in a comment line that, along with the statement "I am sure that 'my' approach", sure as heck looks like you are claiming it as your own.
Not 'a couple of changes'. One minor change, the division by 2, which actually causes problems to the function. Contrary to your suggestion that it 'does NOT skip any viable reduction' it absolutely does, as explained in my previous message. I'm happy to grant that the division by 2 within the loop can reduce the search space - but at the cost of time, since division is an expensive operation. I'd tried that myself in my first version of the function, but discovered that the time saving from reducing the search space was more than offset by the cost of the extra division.
I hope you are not trying to claim that compounding the If statement is a change. That's akin to arguing that 5+2 is functionally/algorithmically different to 2+5
>to furnish an incremental improvement
Which, unfortunately, it doesn't. It's slower, and doesn't reduce all fractions to the lowest ratio.
>I did use your code as a starting point
Starting point? It's the exact same algorithm (barring the one issue I discuss below). Which would be fine if you'd credited it at all, as opposed to putting in a comment line that, along with the statement "I am sure that 'my' approach", sure as heck looks like you are claiming it as your own.
Not 'a couple of changes'. One minor change, the division by 2, which actually causes problems to the function. Contrary to your suggestion that it 'does NOT skip any viable reduction' it absolutely does, as explained in my previous message. I'm happy to grant that the division by 2 within the loop can reduce the search space - but at the cost of time, since division is an expensive operation. I'd tried that myself in my first version of the function, but discovered that the time saving from reducing the search space was more than offset by the cost of the extra division.
I hope you are not trying to claim that compounding the If statement is a change. That's akin to arguing that 5+2 is functionally/algorithmically different to 2+5
>to furnish an incremental improvement
Which, unfortunately, it doesn't. It's slower, and doesn't reduce all fractions to the lowest ratio.
>a base 10 numerical system using limited binary numerical
>representations in a computer
We live with that limitation even when we are not being asked about fractions. So almost all of your (fairly observed) reservations are relevant to scenarios that don't involve fractions. The fractions requirement basically doesn't add any additional issues.
>representations in a computer
We live with that limitation even when we are not being asked about fractions. So almost all of your (fairly observed) reservations are relevant to scenarios that don't involve fractions. The fractions requirement basically doesn't add any additional issues.
WilMead
IS-IT--Management
Apply what you know about prime factorization in fraction to the problem. Above I told you how to reduce ALL fractions.
Applying the information to this sppecialized situation we can easily simplify the process.
This is decimal reduction, so all denominators are Powers of 10. The prime factors of 10 are 2 and 5. This remains true for all powers of ten. 100 = 10^2 = 2^2 * 5^2.
When you factor out the 2's your reduction can stop as soon as your either reduced value is odd. They have no more shared 2 factors.
Since 5 is the only other potentially shared factor, it is the only other number you need to look at for reduction. As with 2, when either number is no longer evenly divisible by 5, you're done.
[tt]
Function fract(n, d)
' factor out common twos.
While (0 = n Mod 2) And (0 = d Mod 2)
n = n / 2
d = d / 2
Wend
' Factor out common fives.
While (0 = n Mod 5) And (0 = d Mod 5)
n = n / 5
d = d / 5
Wend
'Set return string
Fract = Format(n, "0" & "\" & Format(d, "0"
End Function
[/tt]
Division by 2 is not costly, it's a shift. Division by five on the other hand...
Wil Mead
wmead@optonline.net
Applying the information to this sppecialized situation we can easily simplify the process.
This is decimal reduction, so all denominators are Powers of 10. The prime factors of 10 are 2 and 5. This remains true for all powers of ten. 100 = 10^2 = 2^2 * 5^2.
When you factor out the 2's your reduction can stop as soon as your either reduced value is odd. They have no more shared 2 factors.
Since 5 is the only other potentially shared factor, it is the only other number you need to look at for reduction. As with 2, when either number is no longer evenly divisible by 5, you're done.
[tt]
Function fract(n, d)
' factor out common twos.
While (0 = n Mod 2) And (0 = d Mod 2)
n = n / 2
d = d / 2
Wend
' Factor out common fives.
While (0 = n Mod 5) And (0 = d Mod 5)
n = n / 5
d = d / 5
Wend
'Set return string
Fract = Format(n, "0"
& "\" & Format(d, "0"End Function
[/tt]
Division by 2 is not costly, it's a shift. Division by five on the other hand...
Wil Mead
wmead@optonline.net
A division of an integer by an integer 2 is a shift, else we are into floating point division - which is expensive.
Apart from that, your optimisation of the code for this specific requirement works better than my original code (which came from the other direction, in that it was designed for the generic case: feed in any pair* of intN and intD and it still works)
* where intN < intD
Apart from that, your optimisation of the code for this specific requirement works better than my original code (which came from the other direction, in that it was designed for the generic case: feed in any pair* of intN and intD and it still works)
* where intN < intD
WilMead
IS-IT--Management
We both still crumble to the floating point requirements for the large numbers. What happened to that thread about Mod on Huge numbers?
Limiting the search to prime numbers might speed up your process. The problem becomes making the cost of getting the next prime worth it. The cost of testing for prime is way to high to include in the looping.
Try this on a bunch of values.
[tt]
Function fract(n, d)
Dim aPrimes, Prime
aPrimes = Array(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51)
' factor out common primes.
For I = 0 To UBound(aPrimes) ' aPrimes.count?
Prime = aPrimes(I)
If Prime > n Then Exit For
If Prime > d Then Exit For
While (0 = n Mod Prime) And (0 = d Mod Prime)
n = n / Prime
d = d / Prime
Wend
Next
[/tt]
Wil Mead
wmead@optonline.net
Limiting the search to prime numbers might speed up your process. The problem becomes making the cost of getting the next prime worth it. The cost of testing for prime is way to high to include in the looping.
Try this on a bunch of values.
[tt]
Function fract(n, d)
Dim aPrimes, Prime
aPrimes = Array(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51)
' factor out common primes.
For I = 0 To UBound(aPrimes) ' aPrimes.count?
Prime = aPrimes(I)
If Prime > n Then Exit For
If Prime > d Then Exit For
While (0 = n Mod Prime) And (0 = d Mod Prime)
n = n / Prime
d = d / Prime
Wend
Next
[/tt]
Wil Mead
wmead@optonline.net
- Status
Similar threads
- Locked
- Question