06290524.txt 29-Jun-00


Subject: Re: Fraction conversion
From: Eric Kiernan <erickiernan@home.com>

well at the risk of stating the obvious, converting from
  decimal to fraction is quite simple if you are converting
  to a denominator (spelling - but it's the bottom one)  of
  10  (x/10 ).  kind of be a round() deal.  haven't thought
  about it too much, but i suspect to convert to a known
  denominator, it would just be an algebraic ratio, like
  convert 4/10 to x/5 where 4=a,10=b,x=c and 5=d, use cross-
  multiply to say c*b=a*d, and then since we are solving for
  c, it would be c=(a*d)/b.
then i suppose if c was fractional, ( use mod() or % to test
  that ), you would calculate how many digits you needed to
  make it non-fractional, and add that many zeros to the
  denominator.  depends on whether the user wanted to see
  7.5/10 or 75/100.


Subject: Re: Fraction conversion
From: Phil Barnett <dev.nul@iag.net>


Say you needed 4 decimals of depth.
.0005 would equal 5/1000
Any prime number (above 1) that you can divide evenly into
  both the divisor and the denominator can reduce the
  fraction.
In this case, when we get to 5, the above fraction becomes
  1/200.
When a prime reduction works, you start over until you reach
  the last prime smaller than the square root of 1000, which
  ends the reduction process. I limit the prime array by the
  square root of 1000 when I build it. I also limit the
  prime array to 4096 elements, which the last test reaches.
Here is code that does it. This was fun. Nice challenge. ;-)
*+
*+    Source Module => E:\SRC\DEC2FRAC\DEC2FRAC.PRG
*+
*+    Released to Public Domain, June 2000 by Phil Barnett
*+
*+    Functions: Procedure test()
*+               Function dec2frac()
*+               Function GetPrimes()
*+               Function PRB_Int()
*+
*+    Reformatted by Click! 2.03 on Jun-15-2000 at  1:40 am
*+

*+
*+    Procedure test()
*+
procedure test()
? 35.25001, 4, dec2frac( 35.25001, 4 )
? 35.251, 2, dec2frac( 35.251, 2 )
? 35.250, 1, dec2frac( 35.250, 1 )
? -35.250, 1, dec2frac( -35.250, 1 )
? .005, 3, dec2frac( .005, 3 )
? .005, 0, dec2frac( .005, 0 )

? .371, 4, dec2frac( .371, 4 )
? .372, 4, dec2frac( .372, 4 )
? .371, 2, dec2frac( .371, 2 )
? .000400007, 8, dec2frac( .000400007, 8 )
// Wanna see something interesting?
? str( .250, 5, 1 )
// Guess the value before you run it...
return

*+
*+    Function dec2frac()
*+
*+    Called from ( dec2frac.prg )   9 - procedure test()
*+
function dec2frac( nDecimal, nPrecision )
local aPrimes
local nDenominator := 10 ^ nPrecision
local cWhole
local cFraction
local cDecimal
local nDivisor
local x
local lDone
local nPrimes
begin sequence
  nDecimal := PRB_Int( nDecimal,, nPrecision )
  cDecimal := str( nDecimal )
  if -1 > nDecimal .or. nDecimal > 1
    if at( '.', cDecimal ) > 0
      cWhole   := left( cDecimal, at( '.', cDecimal ) - 1 )
      nDivisor := val( substr( cDecimal, ;
        at( '.', cDecimal ) + 1, nPrecision ) )
    else
      cWhole    := cDecimal
      nDivisor  := 0
      cFraction := ''
      break
    endif
  else
    cWhole  := ''
    nDivisor := val( substr( cDecimal, ;
      at( '.', cDecimal ) + 1, nPrecision ) )
  endif
  aPrimes := GetPrimes( nDenominator )
  nPrimes := len( aPrimes )
  lDone := .f.
  do while !lDone
    begin sequence
      for x := 2 to nPrimes
        if nDivisor % aPrimes[ x ] == 0 .and. ;
          nDenominator % aPrimes[ x ] == 0
          nDivisor     /= aPrimes[ x ]
          nDenominator /= aPrimes[ x ]
          break
        endif
      next
      lDone := .t.
    end sequence
  enddo
  if nDivisor == 0

    cFraction := ''
    if empty( cWhole )
      cWhole := '0'
    endif
  else
    cFraction := ltrim( str( nDivisor, 19 ) ) + ;
      '/' + ;
      ltrim( str( nDenominator, 19 ) )
  endif
end sequence
return alltrim( cWhole + ' ' + cFraction )

*+
*+    Function GetPrimes()
*+
*+    Called from ( dec2frac.prg )   1 - function dec2frac()
*+
function GetPrimes( nLimit )
local y
local x
local lPrime
local nStopHere
local aPrime    := array( 2 )
local nPrimeCnt := 2
aPrime[ 1 ] := 1
aPrime[ 2 ] := 2
for x := 3 to nLimit step 2
  lPrime   := .t.
  nStopHere := sqrt( x )
  for y := 3 to nPrimeCnt
    if aPrime[ y ] > nStopHere
      exit
    endif
    if x % aPrime[ y ] == 0
      lPrime := .f.
      exit
    endif
  next
  if lPrime
    ++ nPrimeCnt
    aadd( aPrime, x )
    if len( aPrime ) > 4095
      exit
    endif
  endif
next
return aPrime

#include "COMMON.CH"
*+
*+    Function PRB_Int()
*+
*+    Called from ( dec2frac.prg )   1 - function dec2frac()
*+
function PRB_Int( nNumber, nLength, nDecimals )
local lNegative   := ( nNumber < 0 )
local cSomeString
local nDotat
default nDecimals to 0
default nLength to 19

if lNegative
  nNumber := abs( nNumber )
endif
nNumber += .0000000000000005
cSomeString := alltrim( str( nNumber ) )
nDotat := at( '.', cSomeString )
if nDotat > 0
  cSomeString := left( cSomeString, nDotat + nDecimals )
endif
if lNegative
  cSomeString := '-' + cSomeString
endif
return val( cSomeString )

*+ EOF: DEC2FRAC.PRG

Phil Barnett


Subject: Re: Fraction conversion
From: rlb@fdhoekstra.nl (Richard Bos)

Nice. Unfortunately, because the denominator is always a
  power of ten, you are calculating a lot of primes of which
  only 2 and 5 are ever going to get used. You can simplify
  to this:

// New test procedure included:
procedure test()
?"0.33333:"
?0, padl(rlb_frac1(0.33333,0),15),;
  padl(dec2frac(0.33333,0),15)
?1, padl(rlb_frac1(0.33333,1),15),;
  padl(dec2frac(0.33333,1),15)
?2, padl(rlb_frac1(0.33333,2),15),;
  padl(dec2frac(0.33333,2),15)
?3, padl(rlb_frac1(0.33333,3),15),;
  padl(dec2frac(0.33333,3),15)
?4, padl(rlb_frac1(0.33333,4),15),;
  padl(dec2frac(0.33333,4),15)
?5, padl(rlb_frac1(0.33333,5),15),;
  padl(dec2frac(0.33333,5),15)
?
?"1.625:"
?0, padl(rlb_frac1(1.625,0),15), padl(dec2frac(1.625,0),15)
?1, padl(rlb_frac1(1.625,1),15), padl(dec2frac(1.625,1),15)
?2, padl(rlb_frac1(1.625,2),15), padl(dec2frac(1.625,2),15)
?3, padl(rlb_frac1(1.625,3),15), padl(dec2frac(1.625,3),15)
?4, padl(rlb_frac1(1.625,4),15), padl(dec2frac(1.625,4),15)
?5, padl(rlb_frac1(1.625,5),15), padl(dec2frac(1.625,5),15)
?
?"-2.0512:"
?0, padl(rlb_frac1(-2.0512,0),15),;
  padl(dec2frac(-2.0512,0),15)
?1, padl(rlb_frac1(-2.0512,1),15),;
  padl(dec2frac(-2.0512,1),15)
?2, padl(rlb_frac1(-2.0512,2),15),;
  padl(dec2frac(-2.0512,2),15)
?3, padl(rlb_frac1(-2.0512,3),15),;
  padl(dec2frac(-2.0512,3),15)

?4, padl(rlb_frac1(-2.0512,4),15),;
  padl(dec2frac(-2.0512,4),15)
?5, padl(rlb_frac1(-2.0512,5),15),;
  padl(dec2frac(-2.0512,5),15)
return

function rlb_frac1(number, decimals)
  local sign, whole, divr, denr
  if number>0; sign=1; else; sign=-1; number=-number; endif
  whole=int(number)
  denr=10^decimals; divr=int((number-whole)*denr)
  if divr=0; return alltrim(str(sign*whole,19)); endif
  while denr%2=0 .and. divr%2=0; denr/=2; divr/=2; enddo
  while denr%5=0 .and. divr%5=0; denr/=5; divr/=5; enddo
  if whole=0
    return alltrim(str(divr,19))+"/"+alltrim(str(denr,19))
  endif
return alltrim(str(sign*whole,19))+"
  "+alltrim(str(divr,19))+"/"+ ;
  alltrim(str(denr,19))

Unfortunately, as you see, this fails as miserably on 1/3 as
  does yours, but it is quite a bit faster and does the same
  thing, except for the single case where you don't specify
  enough precision to get a fraction at all; in that case,
  mine gives the integer, yours gives 0. I prefer my
  version, but I think something can be said for yours as
  well... though strangely enough, your function has the
  same behaviour as mine for negative numbers.
I'm currently trying to think of an algorithm that handles
  1/3 as well as 12 3/64, though for the time being vainly.
  Nice challenge, indeed :-p

Richard


Subject: Re: Fraction conversion
From: Phil Barnett <dev.nul@iag.net>

>Nice.
Yeah, but the sieve of eratosthenes is cool, right?
Also, if you ever needed to reduce a fraction that had both
  unknown numbers and was not a decimal based denominator,
  it would still work...
And, PRB_INT() is more like floor() than round() or str(),
  and also makes up for epsilon-delta errors.
And, what about the 19? That was cool too, huh???
>
Unfortunately, because the denominator is always a power of
  ten, you are calculating a lot of primes of which only 2
  and 5 are ever going to get used.
>
(trying valiantly to look smart after reading this...)
> You can simplify to this:
slaps forehead... Duh! How positively rudimentary... There
  are only two primes (greater than 1) in any n^10.
(mumble-grumble...I even used one as an example...)
>
return alltrim(str(sign*whole,19))+;
  " "+alltrim(str(divr,19))+"/"+ ;

>
  alltrim(str(denr,19))
>
Unfortunately, as you see, this fails as miserably on 1/3 as
  does yours, but it is quite a bit faster and does the same
  thing, except for the single case where you don't specify
  enough precision to get a fraction at all; in that case,
  mine gives the integer, yours gives 0. I prefer my
  version, but I think something can be said for yours as
  well... though strangely enough, your function has the
  same behaviour as mine for negative numbers.
>
prb_int() is more like floor() than round() or str().
>
I'm currently trying to think of an algorithm that handles
  1/3 as well as 12 3/64, though for the time being vainly.
  Nice challenge, indeed :-p
>
Maybe we subtract one from the denominator to see if we get
  a very reduced fraction. But, it wouldn't work for
  repeating fractions.

Phil Barnett