OpenEuphoria

Re: bignum progress report

• Posted by Christian.CUVIER at agriculture.gouv.fr Oct 29, 2002
• 449 views

Well, there are whole textbooks on the topic of continued fractions, so
I won't sum them up here :). Just an intuitive sketch:

	A real number x is unambiguously defined by an integer (floor(x) --
call it x_0) and a real number in [0,1[. The latter is the inverse of
some real number above 1, which can be applied the transformation above.
You recursively end up with a sequence of integers that converge towards
x rather fast:

x=x_0+1/(x_1+1/(x_2+1/....)...)

	Here, all x_i are positive integers, except for x_0, which can be any
integer. In real life, the x_i fit into one byte, so Eu could be the
right language to handle these objects - exceot for the wish list ;)

	These are standard continued fractions. If you somehow relax the
constraints (all numerators are 1 and all x_i integers), you get
extended continued fractions, with much greater flexibility, very handy
to compute transcendant functions, but convergence properties will vary.
You'll find quite a few Fortran libraries that rely on this on the Web.

	As for the cube algorithm, it's a 20-year old clever trick by Gosper
and al.; it can handle all elementaty arithmetic on continued fractions,
and more. You can find a good description of how it is implemented, as
well as other useful tips and tricks, at 

http://www.pipeline.com/~hbaker1/hakmem/cf.html

	Actually, this comes from a very old AI memo. Can't remember the
original text-mode address of this, and looks as I lost the .url.

	Regards

	CChris

> 
> Date: Mon, 28 Oct 2002 13:25:15 -0600
> From: Kat <kat at kogeijin.com>
> Subject: Re: bignum progress report
> 
> 
> On 28 Oct 2002, at 16:35, Christian.CUVIER at agriculture.gouv.fr wrote:
> 
> > 
> >  Hi the list!
> > 
> >  Kat, could you tell us how the long string of 0's can happen?
> 
> String of zeros where? The digits in the string math are counted with 
> integers, so you can have 1,073,741,823 digits in your number. Note you will 
> need 8megabytes to email that size number, or 32megabytes to store it in 
> memory in Euphoria. There are strip functions built in, to strip leading and 
> trailing zeros. Also, all results and intermediate calulations must fit into a
>
> numeral 1,073,741,823 digits long. I hope that is accurate enough for most 
> applications.
> 
> >  To put it frankly, I think that continued fractions are good for any
> > precision arithmetic, and Euphoria could be a good language to handle
> > them. Yes, transcendant functions (log, sin,...) are harder to code, but
> > you are much more secure about the precision of the result than with
> > ordibary multiplication, if only because you can directly control it.
> > And it is not that slower, also
> >  I had coded routines in 16-bit assembler for big numbers long ago (I
> > still think asm is best for really serious number crunching); I'd need
> > to rewrite everything to take advantage of MMX2 and Pentium
> > optimizations.
> 
> Assy code would be much faster.
> 
> > Why not use some sort of cube algorithm on continued
> > fractions?
> 
> Hmm? 
> 
> Kat,
> not a mathematician
> 
>