1. Current implementation of exp() is faulty.
include machine.e
include math.e
?atom_to_float64(power(E,20.0))
?atom_to_float64
(485165195.409790277969106830541540558684638988944847254353610800315977996142709740165979850652747349447833789438961)
?atom_to_float64(power(E,12.0))
?atom_to_float64(
162754.7914190039208080052048984867831702092844787207704435562481385967708355437387292882419094316843)
?atom_to_float64(power(E,10.0))
?atom_to_float64(
22026.46579480671651695790064528424436635351261855678107423542635522520281857079257519912096816452590)
?atom_to_float64(power(E,8.0))
?atom_to_float64(
2980.957987041728274743592099452888673755967939132835702208963530387730725173367530157371871490018139)
?atom_to_float64(power(E,6.0))
?atom_to_float64(
403.4287934927351226083871805433882796058998973571292026139671883251511806339934983051788866512126648)
?atom_to_float64(power(E,5.0))
?atom_to_float64(
148.4131591025766034211155800405522796234876675938789890467528451109120648209585760796884094598990211)
?machine_func(26,0)
Results:
{253,231,104,139,8,235,188,65}
{3,232,104,139,8,235,188,65}
{152,124,211,84,22,222,3,65}
{154,124,211,84,22,222,3,65}
{93,5,149,207,157,130,213,64}
{97,5,149,207,157,130,213,64}
{108,12,71,125,234,73,167,64}
{110,12,71,125,234,73,167,64}
{141,192,144,86,220,54,121,64}
{142,192,144,86,220,54,121,64}
{142,51,112,153,56,141,98,64}
{142,51,112,153,56,141,98,64}
So, discrepancies start showing up for values of the argument as small as 6, or
even smaller.
The pasted strings in the code were obtained from Mathematica 5.5 asking for 100
decimal digits of precision. That's way more than hardware can hold.
Suggestion for a more proper implemntation:
exp(x)= (x<=5)
? power(x,E)
: a=log(2)
n=floor(x/a)
x=remainder(x,a)
return exp(x)*power(2,n)
Not tested yet, but must be better.
If you look at the past discussions about math.e (in 2006 or 2007), you'll see
that I had already warned against this problem. Also, some useful constants were
posted there, which may seem worth being included in math.e.
CChris
2. Re: Current implementation of exp() is faulty.
Are my expected values in the unit tests wrong as the unit tests pass. To get
the values for the test, I used Python and took the values they reported and
plugged them into the unit test.
--
Jeremy Cowgar
http://jeremy.cowgar.com
3. Re: Current implementation of exp() is faulty.
Jeremy Cowgar wrote:
>
> Are my expected values in the unit tests wrong as the unit tests pass. To get
> the values for the test, I used Python and took the values they reported and
> plugged them into the unit test.
>
> --
> Jeremy Cowgar
> <a href="http://jeremy.cowgar.com">http://jeremy.cowgar.com</a>
I don't understand either of the two tests. Why rounding the returned value?
Using atom_to_float64() and the parser built in the interpreter is much better.
Don't compare strings, so that you avoid more false negatives. This had already
hit you about deg2rad iirc.
The arguments you used (2 and 2.3) are in the range where power(x,E) returns the
proper value. Try x=10 without rounding.
CChris
4. Re: Current implementation of exp() is faulty.
If you are testing for exact equality, why use atom_to_float64 at all? You are
still getting parsing errors when you do.
Have you tried using Matt's scientific.e library? I think that has a more
accurate parser.
A better solution would be to use C or Python to get your expected values and
store them in a file. The actual value, not a string representation. And then the
unit test would open that file and compare the Euphoria output to the contents of
the file.
Or your C/Python test harness could do the equivalent of atom_to_float64() and
store the byte values as a readable Euphoria sequence and then you could compare
that or cut/paste the values directly into your unit test.
But when you do "?atom_to_float64
(485165195.40979027796910683054154055868463898894484725435361080031597799614270974016
5979850652747349447833789438961)" in your source code, you will get precision
errors due to the limitations of the parser. It becomes an apples and oranges
comparison instead of apples and apples.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
5. Re: Current implementation of exp() is faulty.
CChris wrote:
>
>
> I don't understand either of the two tests. Why rounding the returned value?
> Using atom_to_float64() and the parser built in the interpreter is much
> better.
> Don't compare strings, so that you avoid more false negatives. This had
> already
> hit you about deg2rad iirc.
> The arguments you used (2 and 2.3) are in the range where power(x,E) returns
> the proper value. Try x=10 without rounding.
>
From the deg2rad discussion, it was suggested that I not use atom_to_float64,
and when I tried to, I got figures slightly off. It couldn't make it match any
way I did it except by placing it into a string, however, what I placed into the
string was the same result I was getting from Python. Thus, I think they are
right, or python is wrong too.
--
Jeremy Cowgar
http://jeremy.cowgar.com
6. Re: Current implementation of exp() is faulty.
</snipped>
> But when you do "?atom_to_float64
>
> (485165195.40979027796910683054154055868463898894484725435361080031597799614270974016
> 5979850652747349447833789438961)" in your source code, you will get precision
> errors due to the limitations of the parser. It becomes an apples and oranges
> comparison instead of apples and apples.
>
> --
> A complex system that works is invariably found to have evolved from a simple
> system that works.
> --John Gall's 15th law of Systemantics.
>
> "Premature optimization is the root of all evil in programming."
> --C.A.R. Hoare
>
> j.
Didn't Matt incorporate his parsing improvements to the interpreter?
At any rate, the value provided corresponds to nearly 300 bits of precision.
Even if the lowest 50 are wrong (overly pessimistic), only 17 digits would be
wrong, and the parser should retrieve the exact same value, since a double only
stores 53 bits.
CChris
7. Re: Current implementation of exp() is faulty.
Here's an excerpt from Matt's scientific.e documentation:
"This library evaluates scientific notation to the highest level of precision
possible using Euphoria atoms. An atom can have up to 16 digits of precision. A
number represented by scientific notation could contain up to 17 digits. The 17th
supplied digit may have an effect upon the value of the atom due to rounding
errors in the calculations.
This doesn't mean that if the 17th digit is 5 or higher, you should include it.
The calculations are much more complicated, because a decimal fraction has to be
converted to a binary fraction, and there's not really a one-to-one
correspondence between the decimal digits and the bits in the resulting atom. The
18th or higher digit, however, will never have an effect on the resulting atom. "
Of course, the item of interest is "there's not really a one-to-one
correspondence between the decimal digits and the bits in the resulting atom."
Converting from binary representation to a string is a pretty good compromise.
Converting from string to a binary representation will almost always give you
errors.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
8. Re: Current implementation of exp() is faulty.
CChris wrote:
> Didn't Matt incorporate his parsing improvements to the interpreter?
> At any rate, the value provided corresponds to nearly 300 bits of precision.
> Even if the lowest 50 are wrong (overly pessimistic), only 17 digits would be
> wrong, and the parser should retrieve the exact same value, since a double
> only
> stores 53 bits.
>
> CChris
I've already replied to this, but the main thing is that from atom to string
representation there is a many-to-one correlation. That is, several binary
representations differing only in the least significant bits will translate into
one string representation.
I'm trying to think of the mathematical term for it, but basically that means
that the function is not reversible since you necessarily lose some information
in the conversion and therefore the function cannot be inverted.
Even Matt's scientific.e has limits to parsing precision between decimal/string
representation and the actual binary representation of a calculated number.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
9. Re: Current implementation of exp() is faulty.
Jason Gade wrote:
>
> CChris wrote:
> > Didn't Matt incorporate his parsing improvements to the interpreter?
> > At any rate, the value provided corresponds to nearly 300 bits of precision.
> > Even if the lowest 50 are wrong (overly pessimistic), only 17 digits would
> > be
> > wrong, and the parser should retrieve the exact same value, since a double
> > only
> > stores 53 bits.
> >
> > CChris
>
> I've already replied to this, but the main thing is that from atom to string
> representation there is a many-to-one correlation. That is, several binary
> representations
> differing only in the least significant bits will translate into one string
> representation.
>
> I'm trying to think of the mathematical term for it, but basically that means
> that the function is not reversible since you necessarily lose some
> information
> in the conversion and therefore the function cannot be inverted.
>
> Even Matt's scientific.e has limits to parsing precision between
> decimal/string
> representation and the actual binary representation of a calculated number.
>
> --
> A complex system that works is invariably found to have evolved from a simple
> system that works.
> --John Gall's 15th law of Systemantics.
>
> "Premature optimization is the root of all evil in programming."
> --C.A.R. Hoare
>
> j.
What I was trying to explain is that it is not a problem.
The reason why it is not a problem is that the many variants of a string that
will convert to the same single 8-byte sequence start with the same digits,
usually the first 17 or 18, bar exceptional cases like
0.99999999999999999999999999999999999999 and 1.0.
Since the strings I pasted into my code are way longer than that, the
imprecision should be largely beyond what the parser will ever process. As a
result, in spite of your point, it should return the proper 8-byte sequence.
In order to eliminate the exceptional cases mentioned above, I also tried values
that are not integers, and either fully or not representable as a double. The
discrepancies remain.
CChris
10. Re: Current implementation of exp() is faulty.
CChris wrote:
> What I was trying to explain is that it is not a problem.
> The reason why it is not a problem is that the many variants of a string that
> will convert to the same single 8-byte sequence start with the same digits,
> usually the first 17 or 18, bar exceptional cases like
> 0.99999999999999999999999999999999999999
> and 1.0.
You've got this backwards: the parser will only parse the first 17 decimal
characters into exactly *one* 64-bit double value. However, going from a 64-bit
double value to a string of digits, more than one 64-bit value will match up to
the same string of 16 digits.
> Since the strings I pasted into my code are way longer than that, the
> imprecision
> should be largely beyond what the parser will ever process. As a result, in
> spite of your point, it should return the proper 8-byte sequence.
>
> In order to eliminate the exceptional cases mentioned above, I also tried
> values
> that are not integers, and either fully or not representable as a double. The
> discrepancies remain.
>
> CChris
After the first 17 digits it doesn't matter and anything more is just noise. The
value is not refined further, even if it could be.
I quote Matt again:
"The 18th or higher digit, however, will never have an effect on the resulting
atom."
And:
"there's not really a one-to-one correspondence between the decimal digits and
the bits in the resulting atom."
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
11. Re: Current implementation of exp() is faulty.
Jason Gade wrote:
>
> CChris wrote:
> > What I was trying to explain is that it is not a problem.
> > The reason why it is not a problem is that the many variants of a string
> > that
> > will convert to the same single 8-byte sequence start with the same digits,
> > usually the first 17 or 18, bar exceptional cases like
> > 0.99999999999999999999999999999999999999
> > and 1.0.
>
> You've got this backwards: the parser will only parse the first 17 decimal
> characters
> into exactly *one* 64-bit double value. However, going from a 64-bit double
> value to a string of digits, more than one 64-bit value will match up to the
> same string of 16 digits.
>
> > Since the strings I pasted into my code are way longer than that, the
> > imprecision
> > should be largely beyond what the parser will ever process. As a result, in
> > spite of your point, it should return the proper 8-byte sequence.
> >
> > In order to eliminate the exceptional cases mentioned above, I also tried
> > values
> > that are not integers, and either fully or not representable as a double.
> > The
> > discrepancies remain.
> >
> > CChris
>
> After the first 17 digits it doesn't matter and anything more is just noise.
> The value is not refined further, even if it could be.
>
>
> I quote Matt again:
> "The 18th or higher digit, however, will never have an effect on the resulting
> atom."
>
> And:
>
> "there's not really a one-to-one correspondence between the decimal digits and
> the bits in the resulting atom."
>
> --
> A complex system that works is invariably found to have evolved from a simple
> system that works.
> --John Gall's 15th law of Systemantics.
>
> "Premature optimization is the root of all evil in programming."
> --C.A.R. Hoare
>
> j.
Both quootes are right, but we still don't understand each other.
The pasted in strings come from a professional software specialised in maths
computations, not from anything written in Euphoria. So I'm sure most of the
digits there are not noise. To guard against any cutoff effect, I requested many
more digits than should matter to compute a double.
As I said, that way, even if the last few were noise, it wouldn't matter. All
relevant digits are guaranteed.
Which Euphoria parser are you talking about?
Neither get() nor value() are invoked.
When exwc.exe reads "atom_to_float64(1565146.159101750457681234), it uses an
internal routine, called my_sscanf() in source\scanner.e, which turns a string
into atoms. This routine does not check how many decimal places are given. But
indeed, the 18th digit will very rarely matter at all.
I tried the implementation I suggested, but it is closer to the exact value only
for x>=10 or slightly below. For x greater than say 20, it is almost good.
CChris
12. Re: Current implementation of exp() is faulty.
CChris wrote:
> Both quootes are right, but we still don't understand each other.
>
> The pasted in strings come from a professional software specialised in maths
> computations, not from anything written in Euphoria. So I'm sure most of the
> digits there are not noise.
Heh. Yes, we are not understanding one another! :)
Yes, I know you are using Mathemetica, right? I'm not saying that the digits
*from Mathematica* are noise. I'm saying is that they are noise as an input, not
as an output.
> To guard against any cutoff effect, I requested
> many more digits than should matter to compute a double.
> As I said, that way, even if the last few were noise, it wouldn't matter. All
> relevant digits are guaranteed.
>
> Which Euphoria parser are you talking about?
> Neither get() nor value() are invoked.
> When exwc.exe reads "atom_to_float64(1565146.159101750457681234), it uses an
> internal routine, called my_sscanf() in source\scanner.e, which turns a string
> into atoms. This routine does not check how many decimal places are given. But
> indeed, the 18th digit will very rarely matter at all.
I could be talking about any parser. The error is still there.
>
> I tried the implementation I suggested, but it is closer to the exact value
> only
> for x>=10 or slightly below. For x greater than say 20, it is almost good.
>
> CChris
Here's the problem: You use Mathematica to calculate a value, which it does
using an arbitrary precision and who knows how the number is stored internally.
Then you print out that number which is now in a decimal representation as
represented by a string of ASCII characters.
Then you take said string of ASCII characters and, using Euphoria (value(),
get(), my_sscanf() doesn't matter) and convert those ASCII characters back to a
binary representation of a number. This becomes your "expect" value.
Within the program under test, first a number is converted from ASCII to a
binary representation. Then some operations are performed on that binary
representation (raising e to some power, say). Now, this binary representation
can differ by several least significant bits from your expect value because of
parsing precision errors. But if you converted from double to ASCII and then
printed out the decimal representation, it should match the first 16 significant
figures of your expect string.
I don't have Euphoria handy right now, but if we are still miscommunicating then
I'll try an experiment later and post the results.
Basically, take a number with 17 significant figures. Use atom_to_float64() to
get the byte representation of it. Change the least significant bits by some
number, say 1 or 2 or 4 or 8 or whatever. Then use float64_to_atom() and then
print out the number and compare to your original number.
Maybe I'm wrong.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
13. Re: Current implementation of exp() is faulty.
Oh, and just to clarify: Matt's comments come from his scientific.e library in
the archive, which contains its own number parse routines that I believe are more
accurate than the one built into the interpreter parser.
I believe they would still suffer from conversion errors, just not as
pronounced. Again, I'll have to experiment later.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
14. Re: Current implementation of exp() is faulty.
CChris wrote:
> Results:
> {253,231,104,139,8,235,188,65}
> {3,232,104,139,8,235,188,65}
> {152,124,211,84,22,222,3,65}
> {154,124,211,84,22,222,3,65}
> {93,5,149,207,157,130,213,64}
> {97,5,149,207,157,130,213,64}
> {108,12,71,125,234,73,167,64}
> {110,12,71,125,234,73,167,64}
> {141,192,144,86,220,54,121,64}
> {142,192,144,86,220,54,121,64}
> {142,51,112,153,56,141,98,64}
> {142,51,112,153,56,141,98,64}
You can see what I'm saying right here in your output -- the differences are in
the least significant bits (the first element or two of the sequence). Try
converting these byte sequences to numbers and then print out the decimal
representation of them and see if they match.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
15. Re: Current implementation of exp() is faulty.
CChris wrote:
>
> }}}
<eucode>
> include machine.e
> include math.e
> ?atom_to_float64(power(E,20.0))
> ?atom_to_float64
>
> (485165195.409790277969106830541540558684638988944847254353610800315977996142709740165979850652747349447833789438961)
> ?atom_to_float64(power(E,12.0))
> ?atom_to_float64(
>
> 162754.7914190039208080052048984867831702092844787207704435562481385967708355437387292882419094316843)
> ?atom_to_float64(power(E,10.0))
> ?atom_to_float64(
>
> 22026.46579480671651695790064528424436635351261855678107423542635522520281857079257519912096816452590)
> ?atom_to_float64(power(E,8.0))
> ?atom_to_float64(
>
> 2980.957987041728274743592099452888673755967939132835702208963530387730725173367530157371871490018139)
> ?atom_to_float64(power(E,6.0))
> ?atom_to_float64(
>
> 403.4287934927351226083871805433882796058998973571292026139671883251511806339934983051788866512126648)
> ?atom_to_float64(power(E,5.0))
> ?atom_to_float64(
>
> 148.4131591025766034211155800405522796234876675938789890467528451109120648209585760796884094598990211)
> ?machine_func(26,0)
> </eucode>
{{{
>
> Results:
> {253,231,104,139,8,235,188,65}
> {3,232,104,139,8,235,188,65}
> {152,124,211,84,22,222,3,65}
> {154,124,211,84,22,222,3,65}
> {93,5,149,207,157,130,213,64}
> {97,5,149,207,157,130,213,64}
> {108,12,71,125,234,73,167,64}
> {110,12,71,125,234,73,167,64}
> {141,192,144,86,220,54,121,64}
> {142,192,144,86,220,54,121,64}
> {142,51,112,153,56,141,98,64}
> {142,51,112,153,56,141,98,64}
>
>
> So, discrepancies start showing up for values of the argument as small as 6,
> or even smaller.
Are you certain that it's the implementation of exp and not the parsing
of floating point? You're way beyond the precision that the current
floating point scanner can handle. Try changing to scientific notation.
I just added E+0 to all of your ridiculously precise numbers, and here's
what I got:
{251,231,104,139,8,235,188,65}
{4,232,104,139,8,235,188,65}
{151,124,211,84,22,222,3,65}
{154,124,211,84,22,222,3,65}
{92,5,149,207,157,130,213,64}
{96,5,149,207,157,130,213,64}
{107,12,71,125,234,73,167,64}
{110,12,71,125,234,73,167,64}
{141,192,144,86,220,54,121,64}
{143,192,144,86,220,54,121,64}
{142,51,112,153,56,141,98,64}
{143,51,112,153,56,141,98,64}
Frankly, I have idea how close to Mathematica's result these are. You
never told us what those answers were.
Matt
16. Re: Current implementation of exp() is faulty.
Jason Gade wrote:
>
> Here's an excerpt from Matt's scientific.e documentation:
>
<snip>
Yes. Also, it's only currently used for scientific notation encountered.
It should be fairly easy to make it parse all floating point, though this
would slow things down a little. Not sure where the sweet spot would
be (i.e., when do we lose precision in the current "naive" algorithm).
Matt
17. Re: Current implementation of exp() is faulty.
CChris wrote:
>
>
> Which Euphoria parser are you talking about?
> Neither get() nor value() are invoked.
> When exwc.exe reads "atom_to_float64(1565146.159101750457681234), it uses an
> internal routine, called my_sscanf() in source\scanner.e, which turns a
> string into atoms. This routine does not check how many decimal places are
> given. But indeed, the 18th digit will very rarely matter at all.
Only for very small values of vary rare. :) Somewhat like the very large
values of 2 that yield 2 + 2 = 5.
In fact, my_sscanf usually doesn't make it as far as that before going off
course. It's fine for a few digits, and I'm not sure where it starts losing
it (and it probably depends on the number) but I think it rarely makes it
through all 17.
As I recall, I started looking at binary fractions, and converted them to
decimal representations. Or maybe the other way around. Either way, when
you look at something whose first non-zero is in the 18th digit of precision,
you need at least 54 bits to represent it. Since we never have more than
53, anything after 17 just doesn't matter. And sometimes, the 17th doesn't
matter either.
Matt
18. Re: Current implementation of exp() is faulty.
Matt Lewis wrote:
>
> CChris wrote:
> >
> > }}}
<eucode>
> > include machine.e
> > include math.e
> > ?atom_to_float64(power(E,20.0))
> > ?atom_to_float64
> >
> > (485165195.409790277969106830541540558684638988944847254353610800315977996142709740165979850652747349447833789438961)
> > ?atom_to_float64(power(E,12.0))
> > ?atom_to_float64(
> >
> > 162754.7914190039208080052048984867831702092844787207704435562481385967708355437387292882419094316843)
> > ?atom_to_float64(power(E,10.0))
> > ?atom_to_float64(
> >
> > 22026.46579480671651695790064528424436635351261855678107423542635522520281857079257519912096816452590)
> > ?atom_to_float64(power(E,8.0))
> > ?atom_to_float64(
> >
> > 2980.957987041728274743592099452888673755967939132835702208963530387730725173367530157371871490018139)
> > ?atom_to_float64(power(E,6.0))
> > ?atom_to_float64(
> >
> > 403.4287934927351226083871805433882796058998973571292026139671883251511806339934983051788866512126648)
> > ?atom_to_float64(power(E,5.0))
> > ?atom_to_float64(
> >
> > 148.4131591025766034211155800405522796234876675938789890467528451109120648209585760796884094598990211)
> > ?machine_func(26,0)
> > </eucode>
{{{
> >
> > Results:
> > {253,231,104,139,8,235,188,65}
> > {3,232,104,139,8,235,188,65}
> > {152,124,211,84,22,222,3,65}
> > {154,124,211,84,22,222,3,65}
> > {93,5,149,207,157,130,213,64}
> > {97,5,149,207,157,130,213,64}
> > {108,12,71,125,234,73,167,64}
> > {110,12,71,125,234,73,167,64}
> > {141,192,144,86,220,54,121,64}
> > {142,192,144,86,220,54,121,64}
> > {142,51,112,153,56,141,98,64}
> > {142,51,112,153,56,141,98,64}
> >
> >
> > So, discrepancies start showing up for values of the argument as small as 6,
> > or even smaller.
>
> Are you certain that it's the implementation of exp and not the parsing
> of floating point? You're way beyond the precision that the current
> floating point scanner can handle. Try changing to scientific notation.
> I just added E+0 to all of your ridiculously precise numbers, and here's
> what I got:
>
> {251,231,104,139,8,235,188,65}
> {4,232,104,139,8,235,188,65}
> {151,124,211,84,22,222,3,65}
> {154,124,211,84,22,222,3,65}
> {92,5,149,207,157,130,213,64}
> {96,5,149,207,157,130,213,64}
> {107,12,71,125,234,73,167,64}
> {110,12,71,125,234,73,167,64}
> {141,192,144,86,220,54,121,64}
> {143,192,144,86,220,54,121,64}
> {142,51,112,153,56,141,98,64}
> {143,51,112,153,56,141,98,64}
>
>
> Frankly, I have idea how close to Mathematica's result these are. You
> never told us what those answers were.
>
> Matt
I thought I did....
The pasted value for exp(x) is obtained by ealuating N[Exp[x],100] . When x is
not an integer, it must be entered in fractional form. Otherwise, Mathematica is
aware of the roundoff errors and only returns like 6 or 7 decimal places.
exp(some fraction) can be computed at any precision as a rational approximation.
The process is simply tedious by hand, so I didn't check directly.
CChris
19. Re: Current implementation of exp() is faulty.
Matt Lewis wrote:
>
> Jason Gade wrote:
> >
> > Here's an excerpt from Matt's scientific.e documentation:
> >
> <snip>
>
> Yes. Also, it's only currently used for scientific notation encountered.
> It should be fairly easy to make it parse all floating point, though this
> would slow things down a little. Not sure where the sweet spot would
> be (i.e., when do we lose precision in the current "naive" algorithm).
>
> Matt
Precision is lost when you add roundoff errors together. If, when parsing, you
add 16 numbers of the form n.0E-p, none of them is exactly representable, so you
get 16 times the maximum error, on bad days.
I have coded an alternative which performs arithmetic on the digits of the
string being parsed, so as to never combine inexact results. It supports an exact
mode (givve this many bits of precision) and an auto-round mode (give as much
precision as one can get with the available digits).
I'll benchmark it against scientific.e - it's probably slower and more accurate
- and post the findings. A few other things to do these days...
CChris
20. Re: Current implementation of exp() is faulty.
CChris wrote:
>
> Matt Lewis wrote:
> >
> > Yes. Also, it's only currently used for scientific notation encountered.
> > It should be fairly easy to make it parse all floating point, though this
> > would slow things down a little. Not sure where the sweet spot would
> > be (i.e., when do we lose precision in the current "naive" algorithm).
> >
> > Matt
>
> Precision is lost when you add roundoff errors together. If, when parsing,
> you add 16 numbers of the form n.0E-p, none of them is exactly representable,
> so you get 16 times the maximum error, on bad days.
Yes, this was what I was referring to with respect to the current "naive"
algorithm.
> I have coded an alternative which performs arithmetic on the digits of the
> string being parsed, so as to never combine inexact results. It supports an
> exact mode (givve this many bits of precision) and an auto-round mode (give
> as much precision as one can get with the available digits).
>
> I'll benchmark it against scientific.e - it's probably slower and more
> accurate - and post the findings. A few other things to do these days...
I suspect from this comment that you haven't really looked at scientific.e.
It converts decimal strings to binary, and does manipulations based upon the
binary representation with as much precision as is possible to capture with
a double floating point representation.
Matt
21. Re: Current implementation of exp() is faulty.
Right. And what I was trying to say was that converting from double to string to
double again loses information. Better to do one conversion and compare apples to
apples.
I think that CChris is talking about an arbitrary precision library. Doesn't one
of those already exist in the archive?
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
22. Re: Current implementation of exp() is faulty.
Jason Gade wrote:
>
> Right. And what I was trying to say was that converting from double to string
> to double again loses information. Better to do one conversion and compare
> apples
> to apples.
>
> I think that CChris is talking about an arbitrary precision library.
The parsercan return any nmber of bits in exact mode. Otherwise, it returns as
many bits as the number of digits provided allows in a safe way.
> Doesn't
> one of those already exist in the archive?
There are some:
1/ Extended Precision Arithmetic (A. Tammer)
2/ Big Number Arithmetic (Craig Gilbert), but which is somewhat buggy.
3/ Big Math (Matt)
4/ Calculations with long numbers (D. Money)
They are more or less practical, more or less extensible.
They will cover the basic 4 operations, not sure how they extend to arbitrary
precision real computations - they don't appear to handle anything related to
fuzziness or roundoff. I haven't investigated them thoroughl - I have some
unsubmitted stuff. Still, I prefer using other languages or software to
experiment in these areas.
CChris
>
> --
> A complex system that works is invariably found to have evolved from a simple
> system that works.
> --John Gall's 15th law of Systemantics.
>
> "Premature optimization is the root of all evil in programming."
> --C.A.R. Hoare
>
> j.
23. Re: Current implementation of exp() is faulty.
CChris wrote:
>
> Jason Gade wrote:
> >
> > Right. And what I was trying to say was that converting from double to
> > string
> > to double again loses information. Better to do one conversion and compare
> > apples
> > to apples.
> >
> > I think that CChris is talking about an arbitrary precision library.
>
> The parsercan return any nmber of bits in exact mode. Otherwise, it returns
> as many bits as the number of digits provided allows in a safe way.
Never mind.
Either you are agreeing with me and I just don't see it, or no matter how simply
I try and explain you are missing it.
I thought that we had already resolved the issue.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
24. Re: Current implementation of exp() is faulty.
CChris wrote:
>
> Jason Gade wrote:
> >
> > Right. And what I was trying to say was that converting from double to
> > string
> > to double again loses information. Better to do one conversion and compare
> > apples
> > to apples.
> >
> > I think that CChris is talking about an arbitrary precision library.
>
> The parser can return any nmber of bits in exact mode. Otherwise, it returns
> as many bits as the number of digits provided allows in a safe way.
OK, I thought you were talking about creating doubles. scientific.e could
be extended to however many bits you wanted. I just stopped where doubles
left off.
Matt
25. Re: Current implementation of exp() is faulty.
- Posted by Lucius L. Hilley III <euphoria at unkma?.?om>
May 22, 2008
-
Last edited May 23, 2008
CChris wrote:
>
> Jason Gade wrote:
> >
> > Right. And what I was trying to say was that converting from double to
> > string
> > to double again loses information. Better to do one conversion and compare
> > apples
> > to apples.
> >
> > I think that CChris is talking about an arbitrary precision library.
>
> The parsercan return any nmber of bits in exact mode. Otherwise, it returns
> as many bits as the number of digits provided allows in a safe way.
>
> > Doesn't
> > one of those already exist in the archive?
>
> There are some:
> 1/ Extended Precision Arithmetic (A. Tammer)
> 2/ Big Number Arithmetic (Craig Gilbert), but which is somewhat buggy.
> 3/ Big Math (Matt)
> 4/ Calculations with long numbers (D. Money)
>
> They are more or less practical, more or less extensible.
>
> They will cover the basic 4 operations, not sure how they extend to arbitrary
> precision real computations - they don't appear to handle anything related to
> fuzziness or roundoff. I haven't investigated them thoroughl - I have some
> unsubmitted
> stuff. Still, I prefer using other languages or software to experiment in
> these
> areas.
>
> CChris
>
> >
> > --
> > A complex system that works is invariably found to have evolved from a
> > simple
> > system that works.
> > --John Gall's 15th law of Systemantics.
> >
> > "Premature optimization is the root of all evil in programming."
> > --C.A.R. Hoare
> >
> > j.
I worked on some of that as well. I managed to get past the 4 basic functions.
Worked out some code to do exp() and don't remember if I managed to write code
for ln().
I'll see if I can dig it up.
Lucius L. Hilley III - Unkmar
