🚀 go-pugleaf

In article <48ccra$otn$1@mhade.production.compuserve.com> Oliver Spiesshofer <100334.556@CompuServe.COM> writes:

> Hi. I have a somehow strange question.
> I own a Casio calculator on which you can program in BASIC.
> I'm searching for a program now which can make 12355/12354 out of 
> 1.000080945.

Sorry to disappoint you, but the shortest answer to your question (well,
it is not really a question :-) is NO. There is no such program. Period.

> As those calculators round the last bit of the number (as you can 
> the with the first example, 1.000080945 * 12354 = 12354.99999),
> so for some calculations it doesn't work, and for the rest it 
> takes centuries. I woud have to make an aproximisation, but i 
> don't know how.

Another reader (Michael Hardy, hardy@minnehaha.stat.umn.edu) already pointed
out that:

> Suppose you want to make a fraction out of pi:

	[nice method to approximate pi deleted]

> 	If we cut this off right here with the last ``1'', it simplifies
> to 104348/33215, which is a decimal _approximation_ of pi.  (Correct to
> nine places after the decimal point, which is _extremely_ good for a
> denominator as small as 33215.)

The key word here (and you already intuited this) is *approximation*.
Computers are only good to store finite amounts of information (gee,
even this computer I am working on has only 64 MB of RAM ... a lot but
far from infinite ...); therefore, you can't store the complete decimal
representation of a number. This is what kills you: you can't get the right
answer starting from the wrong question. If you wanted a hypothetical program
to tell you that the fraction you are looking for is 1/12354 (you can always
simplify the problem by making the value between 0 and 1), you should give it
the right value of 1/12354, which is

0.00008094544277157196049862392747288327667152339323296098429658410231503966326695807026064432572446171280556904646268415088230532621013436943500080945442771571960498623927472883276671523393232960984296584102315039663266958070260644325724461712805569046462684150882305326210134369435 .....

ad infinitum. As this is impossible, so is the task of (starting from a finite
decimal approximation of a fraction) getting the right numerator and
denominator.

Well, not *ALL* is lost: you can still solve the problem if, instead of
giving the program a finite decimal expansion, you give it the two parts
of the infinite expansion of the fraction: the period and the [oops, I
don't know the english word for it!] ... well, `what comes before the
period'. In the case at hand, the period of 1/12354 is

00080945442771571960498623927472883276671523393232960984296584102315039663266958070260644325724461712805569046462684150882305326210134369435

and its ... well, `what comes before the period' (is it called pre-period?
To simplify, I will use this word, although it is very likely to be incorrect)
is 0 (yes, there were four 0's right after the decimal point; three are in the
period and the other is in the pre-period).

It is possible to write a computer program that, given the period and the
pre-period of a fraction will compute the numerator and the denominator.
Michael already gives some clues about the process for this in his other
posting; take a look at it. He also mentions that the fraction you would get
in this way may not be in minimal form, and you would need to simplify it;
take his advice on reading about Euclid's algorithm (to compute the greatest
common divisor of two natural numbers, in this case the numerator and
denominator of the fraction to simplify).

Another question you might be asking yourself is: "How the h... am I going to
store a period with 140 digits? My computer only can hold numbers with up to
12 digits!". If this is the case, it means you already learned something ;-)
Let us just say that, instead of storing the period and pre-period in one
integer variable, you use an array of integers, and store the `digits'
(although, instead of base 10, you can use a bigger base to reduce the amount
of memory needed). Needless to say, this has the complication that you have
to handle the arithmetic operations yourself ... how do you add two big
numbers stored in this fashion?

As you can see, working beyond the precission of a computer (calculator,
whatever) is not trivial, but can be done. I recall having assigned projects
to my students in an introductory Comp. Sci. course (2nd year Engineering
students, by the way) to "Compute pi/e/sqrt(2) with 1000 digits", or to
"find a prime number with 30 digits".

Hope this helps.

Regards,

Luis

> Oliver Spiesshofer

> Please e-mail to me.

I will.