OpenEuphoria

fraclib.e

• Posted by jbrown1050 at hotpop.com Jan 21, 2003
• 524 views

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