1. fraclib.e
I'm wrote this very simple lib, which gives infinite precision for rational
numbers by storing numbers as fractions, i.e. "1/3 * 3" (actually,
"f_mul({1,3}, {3,1})" using my lib) returns 1, rather than 0.9999999999
It stores fractions as a 2 element biginteger sequence. (A biginteger
is currently an atom thats restricted to whole numbers, I eventually plan
to add a bignum library to it, so you are not limited by the +/-1e300
size of an atom.)
If you try out this line, "? atom_to_f(f_to_atom({1,3}))", via my lib,
you'll find it takes a VERY long time to compute. This is because my
reduce() function is not very optimized. Any one have any ideas on how it
could be made faster?
TIA,
jbrown
My lib is pasted into my signature space at the bottom of this email.
--
include get.e
include misc.e
global type biginteger(object a)
if not atom(a) then
return 0
end if
if floor(a) != a then
return 0
end if
return 1
end type
global type fraction(object s)
if not sequence(s) then
return 0
end if
if length(s) != 2 then
return 0
end if
if not(biginteger(s[1]) and biginteger(s[2])) then
return 0
end if
return 1
end type
function gcd(biginteger num1, biginteger num2)
biginteger gcd_val
if num1 > num2 then
gcd_val = num1
else
gcd_val = num2
end if
while remainder(num1, gcd_val) != 0
or remainder(num2, gcd_val) != 0 do
gcd_val -= 1
end while
return gcd_val
end function
function reduce(fraction f)
if f[2] = 0 then
f[2] /= 0 --trigger an error here.
end if
return f / gcd(f[1], f[2])
end function
global function f_mul(fraction f1, fraction f2)
return reduce({f1[1]*f2[1], f1[2]*f2[2]})
end function
global function f_div(fraction f1, fraction f2)
return f_mul(f1, {f2[2], f2[1]})
end function
global function f_add(fraction f1, fraction f2)
biginteger f1_dem, f2_dem
f1_dem = f1[2]
f2_dem = f2[2]
f1 *= f2_dem
f2 *= f1_dem
return reduce({f1[1]+f2[1], f1[2]})
end function
global function f_sub(fraction f1, fraction f2)
biginteger f1_dem, f2_dem
f1_dem = f1[2]
f2_dem = f2[2]
f1 *= f2_dem
f2 *= f1_dem
return reduce({f1[1]-f2[1], f1[2]})
end function
global function f_to_atom(fraction f)
return f[1]/f[2]
end function
global function f_to_string(fraction f)
return sprintf("%d/%d", f)
end function
global function string_to_f(sequence s)
--if we had a scanf(), i could just get it via scanf("%d/%d")! sheesh!
sequence v
integer i
i = find('/', s)
if i = 0 then
return ""
end if
v = {0,0}
v[1] = value(s[1..i-1])
v[2] = value(s[i+1..length(s)])
if v[1][1] !=0 or v[2][1] != 0 then
return ""
end if
v[1] = v[1][2]
v[2] = v[2][2]
if not fraction(v) then
return ""
end if
return v
end function
global function atom_to_f(atom a)
sequence s, t
integer i, si
--base_dem is the 1 followed by zeros,
--base_num is the decimal part as a numerator,
--whole_num should be obvious (whole number part of a)
biginteger base_dem, base_num, whole_num
if biginteger(a) then
--ah, the easy part ;]
return {a, 1}
else
--aw, the hard part :[
s = sprint(a)
if s[1] = '-' then
--preserve the sign in case of '-0.'
si = -1
s = s[2..length(s)]
else
si = 1
end if
i = find('.', s)
t = value(s[1..i-1])
if t[1] = 0 then
whole_num = t[2]
else
return 0
end if
t = value(s[i+1..length(s)])
if t[1] = 0 then
base_num = t[2]
else
return 0
end if
t = value("1"&repeat('0', length(s[i+1..length(s)])))
if t[1] = 0 then
base_dem = t[2]
else
return 0
end if
--guarrentted not to be zero unless a is, so we can safely put it here.
--(bases_dem works as well in theory, but I didnt test it and I think
--that its a bad idea since the numerator should have the sign in
--any case, as I understand basic math that is.)
base_num *= si
return f_add({whole_num, 1}, {base_num, base_dem})
end if
end function
2. Re: fraclib.e
Hello Jim, you wrote:
> I'm wrote this very simple lib, which gives infinite precision for rational
> numbers by storing numbers as fractions, i.e. "1/3 * 3" (actually,
> "f_mul({1,3}, {3,1})" using my lib) returns 1, rather than 0.9999999999
Very nice! I also started such a lib, which isn't finished yet. It seems
that we are often interested in the same things. 
> It stores fractions as a 2 element biginteger sequence. (A biginteger
> is currently an atom thats restricted to whole numbers,
I use 3 element biginteger (called "hugeint" by me ) sequences, so
that my lib also can handle mixed numbers.
> I eventually plan
> to add a bignum library to it, so you are not limited by the +/-1e300
> size of an atom.)
>
> If you try out this line, "? atom_to_f(f_to_atom({1,3}))", via my lib,
> you'll find it takes a VERY long time to compute. This is because my
> reduce() function is not very optimized.
Precisely speaking, it's your gcd() function, called by reduce(). I
recommend using the Euclidean Algorithm to calculate the Greatest Common
Divisor (see my function gcd2() below).
> Any one have any ideas on how it could be made faster?
>
> TIA,
> jbrown
Best regards,
Juergen
>
> My lib is pasted into my signature space at the bottom of this email.
> --
> include get.e
> include misc.e
>
> global type biginteger(object a)
> if not atom(a) then
> return 0
> end if
> if floor(a) != a then
> return 0
> end if
> return 1
> end type
>
> global type fraction(object s)
> if not sequence(s) then
> return 0
> end if
> if length(s) != 2 then
> return 0
> end if
> if not(biginteger(s[1]) and biginteger(s[2])) then
> return 0
> end if
> return 1
> end type
>
> function gcd(biginteger num1, biginteger num2)
> biginteger gcd_val
> if num1 > num2 then
> gcd_val = num1
> else
> gcd_val = num2
> end if
> while remainder(num1, gcd_val) != 0
> or remainder(num2, gcd_val) != 0 do
> gcd_val -= 1
> end while
> return gcd_val
> end function
function abs (atom x)
if x < 0 then
return -x
end if
return x
end function
global function gcd2 (biginteger p, biginteger q)
-- returns the greatest common divisor of p and q (Euclidean Algorithm)
-- in : p, q: integers
-- out: nonnegative integer (>= 0)
-- note: gcd2(p, 0) = gcd2(p, p) = abs(p)
-- The number of steps needed to arrive at the greatest common
-- divisor for two numbers is <= 5 times the number of digits in
-- the number with the smaller absolute value, i.e.:
-- n = min(abs(p), abs(q))
-- steps <= 5*(floor(log10(n))+1)
-- The worst case occurs when the algorithm is applied to two
-- consecutive Fibonacci numbers.
-- [ by JuLu,
-- after http://mathworld.wolfram.com/EuclideanAlgorithm.html ]
biginteger r
while q do
r = remainder(p, q)
p = q
q = r
end while
return abs(p)
end function
> function reduce(fraction f)
> if f[2] = 0 then
> f[2] /= 0 --trigger an error here.
> end if
> return f / gcd(f[1], f[2])
> end function
>
> global function f_mul(fraction f1, fraction f2)
> return reduce({f1[1]*f2[1], f1[2]*f2[2]})
> end function
>
> global function f_div(fraction f1, fraction f2)
> return f_mul(f1, {f2[2], f2[1]})
> end function
>
> global function f_add(fraction f1, fraction f2)
> biginteger f1_dem, f2_dem
> f1_dem = f1[2]
> f2_dem = f2[2]
> f1 *= f2_dem
> f2 *= f1_dem
> return reduce({f1[1]+f2[1], f1[2]})
> end function
>
> global function f_sub(fraction f1, fraction f2)
> biginteger f1_dem, f2_dem
> f1_dem = f1[2]
> f2_dem = f2[2]
> f1 *= f2_dem
> f2 *= f1_dem
> return reduce({f1[1]-f2[1], f1[2]})
> end function
>
> global function f_to_atom(fraction f)
> return f[1]/f[2]
> end function
>
> global function f_to_string(fraction f)
> return sprintf("%d/%d", f)
> end function
>
> global function string_to_f(sequence s)
> --if we had a scanf(), i could just get it via scanf("%d/%d")! sheesh!
> sequence v
> integer i
> i = find('/', s)
> if i = 0 then
> return ""
> end if
> v = {0,0}
> v[1] = value(s[1..i-1])
> v[2] = value(s[i+1..length(s)])
> if v[1][1] !=0 or v[2][1] != 0 then
> return ""
> end if
> v[1] = v[1][2]
> v[2] = v[2][2]
> if not fraction(v) then
> return ""
> end if
> return v
> end function
>
> global function atom_to_f(atom a)
> sequence s, t
> integer i, si
> --base_dem is the 1 followed by zeros,
> --base_num is the decimal part as a numerator,
> --whole_num should be obvious (whole number part of a)
> biginteger base_dem, base_num, whole_num
> if biginteger(a) then
> --ah, the easy part ;]
> return {a, 1}
> else
> --aw, the hard part :[
> s = sprint(a)
> if s[1] = '-' then
> --preserve the sign in case of '-0.'
> si = -1
> s = s[2..length(s)]
> else
> si = 1
> end if
> i = find('.', s)
> t = value(s[1..i-1])
> if t[1] = 0 then
> whole_num = t[2]
> else
> return 0
> end if
> t = value(s[i+1..length(s)])
> if t[1] = 0 then
> base_num = t[2]
> else
> return 0
> end if
> t = value("1"&repeat('0', length(s[i+1..length(s)])))
> if t[1] = 0 then
> base_dem = t[2]
> else
<snip>
3. Re: fraclib.e
On Tue, 21 Jan 2003 00:40:27 -0500, jbrown1050 at hotpop.com wrote:
>Any one have any ideas on how it
>could be made faster?
Use Euclids algorithm:
function gcd(biginteger p, biginteger q)
biginteger tmp
while q do
if p>q then
tmp=3Dq
q=3Dp
p=3Dtmp
end if
q=3Dremainder(q,p)
end while
return p
end function
Probably 3 or 4% faster, or something, Hehe.
Pete
PS I do want to know exactly how long that atom_to_f(f_to_atom({1,3}))
took (if it ever finished), and the new speed
4. Re: fraclib.e
On Tue, 21 Jan 2003 10:28:04 +0100, Juergen Luethje <eu.lue at gmx.de>
wrote:
>global function gcd2 (biginteger p, biginteger q)
Similar to mine, but yours is neater, better commented, and works with
negative numbers 
=20
> -- The number of steps needed to arrive at the greatest common
> -- divisor for two numbers is <=3D 5 times the number of digits in
> -- the number with the smaller absolute value, i.e.:
> -- n =3D min(abs(p), abs(q))
> -- steps <=3D 5*(floor(log10(n))+1)
Quite fast then.
> -- The worst case occurs when the algorithm is applied to two
> -- consecutive Fibonacci numbers.
> -- [ by JuLu,
> -- after http://mathworld.wolfram.com/EuclideanAlgorithm.html ]
Hairy stuff indeed.
Pete
5. Re: fraclib.e
Hello Pete, you wrote:
> On Tue, 21 Jan 2003 10:28:04 +0100, Juergen Luethje <eu.lue at gmx.de>
> wrote:
>
>> global function gcd2 (biginteger p, biginteger q)
>
> Similar to mine, but yours is neater, better commented, and works with
> negative numbers
Thanks.
Well, it's part of my private 'math.e', so I tried to make it as
generally usable as I could.
BTW: I think it would be good, if the official Euphoria distribution
includes a 'math.e' library file. This c/should include the trig
functions from 'misc.e', and at least the most common things, such as:
-- global constant
E = 2.718281828459045235
-- global functions
abs()
sgn()
ceil()
trunc()
frac()
round_half_up()
round_half_even()
min()
max()
and why not also
gcd()
lcm() [least common multiple]?
At the moment, people all have their own abs(), round() and gcd()
functions and so on. That doesn't make much sense to me.
Euphoria wants to compete with BASIC, doesn't it?
On the other hand, for a highly skilled programmer like Rob it is *very*
easy to write these functions. This even isn't necessary, because most
of them (if not all) are on the 'Recent Contributions' page (maybe they
are all in Ricardos 'genfunc.zip') -- or on your or my hard disk.
>> -- The number of steps needed to arrive at the greatest common
>> -- divisor for two numbers is <= 5 times the number of digits in
>> -- the number with the smaller absolute value, i.e.:
>> -- n = min(abs(p), abs(q))
>> -- steps <= 5*(floor(log10(n))+1)
> Quite fast then.
Yep.
>> -- The worst case occurs when the algorithm is applied to two
>> -- consecutive Fibonacci numbers.
>> -- [ by JuLu,
>> -- after http://mathworld.wolfram.com/EuclideanAlgorithm.html ]
> Hairy stuff indeed.
I believe that the theory of this stuff has more hairs, than there are
left on my head. )
On the other hand, practically speaking, the Euclidean Algorithm is
simple, short, fast, and elegant. Interesting, isn't it?
> Pete
Best regards,
Juergen
--
/"\ ASCII ribbon | while not asleep do
\ / campain against | sheep += 1
X HTML e-mail and | end while
/ \ news |
6. Re: fraclib.e
On Tue, Jan 21, 2003 at 10:59:13AM +0000, Pete Lomax wrote:
>
> On Tue, 21 Jan 2003 00:40:27 -0500, jbrown1050 at hotpop.com wrote:
>
> >Any one have any ideas on how it
> >could be made faster?
>
> Use Euclids algorithm:
>
<snip>
>
> Probably 3 or 4% faster, or something, Hehe.
A lot more than that apparently. ;]
Thanks!!
>
> Pete
> PS I do want to know exactly how long that atom_to_f(f_to_atom({1,3}))
> took (if it ever finished), and the new speed
The old one never finished.
The new one, appears to finish instantly. (No I did not benchmark it.)
jbrown
>
> ==^^===============================================================
> This email was sent to: jbrown1050 at hotpop.com
>
>
> TOPICA - Start your own email discussion group. FREE!
--
/"\ ASCII ribbon
\ / campain against
X HTML e-mail and
/*\ news and unneeded MIME
7. Re: fraclib.e
On Tue, Jan 21, 2003 at 10:28:04AM +0100, Juergen Luethje wrote:
>
> Hello Jim, you wrote:
>
> > I'm wrote this very simple lib, which gives infinite precision for rational
> > numbers by storing numbers as fractions, i.e. "1/3 * 3" (actually,
> > "f_mul({1,3}, {3,1})" using my lib) returns 1, rather than 0.9999999999
>
> Very nice! I also started such a lib, which isn't finished yet. It seems
> that we are often interested in the same things.
;-]
>
> > It stores fractions as a 2 element biginteger sequence. (A biginteger
> > is currently an atom thats restricted to whole numbers,
>
> I use 3 element biginteger (called "hugeint" by me ) sequences, so
> that my lib also can handle mixed numbers.
>
Ah, mine handles those as inproper fractions. (1 and 1/3 is stored internally
as {4, 3} rather than {1, 1, 3}, for example.) I chose this route for
simplicity.
How large can a hugeint be? Is it just an atom used as an integer, or is it
a more special type of number (i.e. a bignum all to itself)?
> > I eventually plan
> > to add a bignum library to it, so you are not limited by the +/-1e300
> > size of an atom.)
> >
> > If you try out this line, "? atom_to_f(f_to_atom({1,3}))", via my lib,
> > you'll find it takes a VERY long time to compute. This is because my
> > reduce() function is not very optimized.
>
> Precisely speaking, it's your gcd() function, called by reduce(). I
> recommend using the Euclidean Algorithm to calculate the Greatest Common
> Divisor (see my function gcd2() below).
Thanks. I saw the one from Pete Lomax first, so I'm using his version instead.
(Not that it really matters, as the 2 are the same thing.)
>
> > Any one have any ideas on how it could be made faster?
> >
> > TIA,
> > jbrown
>
> Best regards,
> Juergen
>
<snip>
BTW, what would be really useful here, is a way to make a custom type
which allows one to redefine the math operators, so I could do "f1 + f2"
rather than "f_add(f1, f2)", but have the 2 mean the same thing. (I have a
very simple parser to handle this for me however, to be added to Dredge, a.k.a.
Euphoria++).
jbrown
--
/"\ ASCII ribbon
\ / campain against
X HTML e-mail and
/*\ news and unneeded MIME
8. Re: fraclib.e
On Tue, Jan 21, 2003 at 01:28:23PM -0300, rforno at tutopia.com wrote:
>
> Have you tried the free ABC programming language from the Netherlands? They
> do this kind of thing apparently with infinite precision. I don't know how
> they do that. Maybe you could contact them to learn the basis of their
> algorithm.
> Regards.
<snip>
I read about that once (in this list), thats what inspired me to write my lib.
In any case it works speedily now, thanks to Pete and Juergen.
jbrown
--
/"\ ASCII ribbon
\ / campain against
X HTML e-mail and
/*\ news and unneeded MIME
9. Re: fraclib.e
Actually, yours doesnt work for negative fractions (it takes forever it
seems :[ ) so I'm using Juergen's now. (Modified so it needs no external
abs() function, of course ;])
jbrown
On Tue, Jan 21, 2003 at 02:47:28PM -0500, jbrown1050 at hotpop.com wrote:
>
> On Tue, Jan 21, 2003 at 10:59:13AM +0000, Pete Lomax wrote:
> >
> > On Tue, 21 Jan 2003 00:40:27 -0500, jbrown1050 at hotpop.com wrote:
> >
> > >Any one have any ideas on how it
> > >could be made faster?
> >
> > Use Euclids algorithm:
> >
> <snip>
> >
> > Probably 3 or 4% faster, or something, Hehe.
>
> A lot more than that apparently. ;]
> Thanks!!
>
> >
> > Pete
>
> > PS I do want to know exactly how long that atom_to_f(f_to_atom({1,3}))
> > took (if it ever finished), and the new speed
>
> The old one never finished.
>
> The new one, appears to finish instantly. (No I did not benchmark it.)
>
> jbrown
>
--
/"\ ASCII ribbon
\ / campain against
X HTML e-mail and
/*\ news and unneeded MIME
10. Re: fraclib.e
Hello Jim, you wrote:
> On Tue, Jan 21, 2003 at 10:28:04AM +0100, Juergen Luethje wrote:
<snipped by a human>
>>> It stores fractions as a 2 element biginteger sequence. (A biginteger
>>> is currently an atom thats restricted to whole numbers,
>>
>> I use 3 element biginteger (called "hugeint" by me ) sequences, so
>> that my lib also can handle mixed numbers.
>
> Ah, mine handles those as inproper fractions. (1 and 1/3 is stored internally
> as {4, 3} rather than {1, 1, 3}, for example.) I chose this route for
> simplicity.
Simplicity is an advantage, of course.
On the other hand, we can do nice things with mixed numbers, e.g.
easily calculate with the time, and automatically get the result in an
appropriate format.
Say you start a job at half past seven AM, and it ends at a quater to
five PM. How long did it take?
elapsed = f_sub({16, 45, 60}, {7, 30, 60})
=> elapsed = {9, 15, 60} (9 hours and 15 minutes)
To achive this goal, in my lib the result of f_sub() and f_add() is
*not* automatically reduce()d, if the denominators of both numbers are
the same.
> How large can a hugeint be? Is it just an atom used as an integer,
Yes, that's it. Just another word for what you call 'biginteger'.
<snipped by a human>
> BTW, what would be really useful here, is a way to make a custom type
> which allows one to redefine the math operators, so I could do "f1 + f2"
> rather than "f_add(f1, f2)", but have the 2 mean the same thing. (I have a
> very simple parser to handle this for me however, to be added to Dredge,
> a.k.a.
> Euphoria++).
Interesting! Is it ready for public release?
Best regards,
Juergen
--
/"\ ASCII ribbon | while not asleep do
\ / campain against | sheep += 1
X HTML e-mail and | end while
/ \ news |
11. Re: fraclib.e
On Wed, Jan 22, 2003 at 11:43:04AM +0100, Juergen Luethje wrote:
>
> Hello Jim, you wrote:
>
> > On Tue, Jan 21, 2003 at 10:28:04AM +0100, Juergen Luethje wrote:
>
> <snipped by a human>
>
> >>> It stores fractions as a 2 element biginteger sequence. (A biginteger
> >>> is currently an atom thats restricted to whole numbers,
> >>
> >> I use 3 element biginteger (called "hugeint" by me ) sequences, so
> >> that my lib also can handle mixed numbers.
> >
> > Ah, mine handles those as inproper fractions. (1 and 1/3 is stored
> > internally
> > as {4, 3} rather than {1, 1, 3}, for example.) I chose this route for
> > simplicity.
>
> Simplicity is an advantage, of course.
> On the other hand, we can do nice things with mixed numbers, e.g.
> easily calculate with the time, and automatically get the result in an
> appropriate format.
> Say you start a job at half past seven AM, and it ends at a quater to
> five PM. How long did it take?
> elapsed = f_sub({16, 45, 60}, {7, 30, 60})
> => elapsed = {9, 15, 60} (9 hours and 15 minutes)
>
> To achive this goal, in my lib the result of f_sub() and f_add() is
> *not* automatically reduce()d, if the denominators of both numbers are
> the same.
Ah interesting. My lib, however, is only intended in specialied math programs
which need infinite accuracy of rational numbers - not as a generic lib.
Also, I'm trying to figure out how to represent such things as Pi and e
(and other known irrational numbers) in another math lib, so you can do math
with those numbers, but still get accurate results, or at least accurate
calculations. (I.e. ((1/3)*Pi)/(1/3)) on my calculator does not give Pi as it
should, but I plan to make a lib for which it does.)
P.S. I know Pi is not irrational, but if its several trillion digits long,
I doubt that many people would want to compute that much in a home PC.
>
> > How large can a hugeint be? Is it just an atom used as an integer,
>
> Yes, that's it. Just another word for what you call 'biginteger'.
Ah I see. Ultimately we'll want a bignum of course. ;]
>
> <snipped by a human>
>
> > BTW, what would be really useful here, is a way to make a custom type
> > which allows one to redefine the math operators, so I could do "f1 + f2"
> > rather than "f_add(f1, f2)", but have the 2 mean the same thing. (I have a
> > very simple parser to handle this for me however, to be added to Dredge,
> > a.k.a.
> > Euphoria++).
>
> Interesting! Is it ready for public release?
No, not quite yet, sorry.
>
> Best regards,
> Juergen
>
jbrown
> --
> /"\ ASCII ribbon | while not asleep do
> \ / campain against | sheep += 1
> X HTML e-mail and | end while
> / \ news |
>
>
>
> TOPICA - Start your own email discussion group. FREE!
--
/"\ ASCII ribbon
\ / campain against
X HTML in e-mail and
/*\ news, and unneeded MIME
12. Re: fraclib.e
Hello Matt and Jim!
Matt wrote:
>> From: jbrown1050 at hotpop.com [mailto:jbrown1050 at hotpop.com]
>
>> P.S. I know Pi is not irrational, but if its several trillion
>> digits long,
>> I doubt that many people would want to compute that much in a home PC.
>
> In fact, pi *is* irrational. There are no integers a and b such that pi = a
> / b. Beyond that, pi is transcendental (as opposed to algegbraic). This
> means that pi cannot be exactly described by any polynomial (i.e., sqrt(2)
> can be described by x^2 - 2 = 0 -- it is *irrational*, but *not*
> transcendental).
ACK.
Jim, here are some formulas for you to calculate Pi:
http://mathworld.wolfram.com/PiFormulas.html
Beast regards,
Juergen
--
/"\ ASCII ribbon | while not asleep do
\ / campain against | sheep += 1
X HTML e-mail and | end while
/ \ news |
