1. bigint/bugnum library
- Posted by bugmagnet Jul 09, 2013
- 1947 views
I notice that Lucius was developing a bignums library some years ago. Did anything come of that? Is there support for bignums in Euphoria? I know, I should RTFM but I'm reading the friendy forum instead.
bugmagnet
2. Re: bigint/bugnum library
- Posted by TheresNoTime Jul 10, 2013
- 1927 views
Recently I was looking for something like this and have not found. I had to use VB.NET 2010 for my program - http://sourceforge.net/projects/pwfh/ Maybe I'm too early to despair? I do not mind porting it to the Euphoria, because .NET too greedy to resources. That tiny program starts a few seconds!
3. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 10, 2013
- 1907 views
I notice that Lucius was developing a bignums library some years ago. Did anything come of that? Is there support for bignums in Euphoria? I know, I should RTFM but I'm reading the friendy forum instead.
bugmagnet
AFAIK, this was the last word on it. http://sourceforge.net/mailarchive/message.php?msg_id=29162387
In short, the idea was well received but the last known implementation was found lacking in a few areas, and no one has had time to to fix it (or prepare an alternative library).
A feature request for this is still open. http://openeuphoria.org/ticket/760.wc
4. Re: bigint/bugnum library
- Posted by useless_ Jul 10, 2013
- 1931 views
I notice that Lucius was developing a bignums library some years ago. Did anything come of that? Is there support for bignums in Euphoria? I know, I should RTFM but I'm reading the friendy forum instead.
bugmagnet
AFAIK, this was the last word on it. http://sourceforge.net/mailarchive/message.php?msg_id=29162387
In short, the idea was well received but the last known implementation was found lacking in a few areas, and no one has had time to to fix it (or prepare an alternative library).
A feature request for this is still open. http://openeuphoria.org/ticket/760.wc
The "money type of numbers" is BCD (binary coded decimal), where each 4 bits counts 0 to 9, and there's usually 4 bits used per 8bit computer bytes. Some cpus have a native bcd mode. I've used Lucius's lib, moving it into each include file as i downloaded new Euphoria versions, just like strtok.e and win32fil.e and titlebar.e and a few others with important functions.
There's various versions floating around: bcd_math.asm (June, 1997; by Morten Elling; limited to 48,000 digits), big.e, bigfixed.e[different versions], bigfixedmath.e, bigmath[different versions], bignum, and bignum_64bit. I leave it to Lucius to point out which is best for your particular needs. Or i can upload them all and you decide?
useless
5. Re: bigint/bugnum library
- Posted by bugmagnet Jul 10, 2013
- 1914 views
There's various versions floating around: bcd_math.asm (June, 1997; by Morten Elling; limited to 48,000 digits), big.e, bigfixed.e[different versions], bigfixedmath.e, bigmath[different versions], bignum, and bignum_64bit. I leave it to Lucius to point out which is best for your particular needs. Or i can upload them all and you decide?
Hmmmmm .... maybe I should have waited before starting up on eu-bignum. Oh well, too late now. Mind you, the C library that eu-bignum is/will be based on only does integers. I've got a working javascript port at js-bignum (ignore the string-based version).
Bugmagnet
6. Re: bigint/bugnum library
- Posted by Spock Jul 12, 2013
- 1788 views
Out of curiosity, does anyone know the highest integer value at which Eu atoms are still stable for integral amounts. I might have to write a conversion program, which deals with monetary values, for my company and I'd rather avoid having to use a bignum library, if at all possible. A Eu integer maxes out at a billion, right? So if each integral represents one cent the integer would be useful for values up to $10 million. How much higher is the limit using atoms?
Spock
7. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 12, 2013
- 1798 views
Out of curiosity, does anyone know the highest integer value at which Eu atoms are still stable for integral amounts. I might have to write a conversion program, which deals with monetary values, for my company and I'd rather avoid having to use a bignum library, if at all possible. A Eu integer maxes out at a billion, right? So if each integral represents one cent the integer would be useful for values up to $10 million. How much higher is the limit using atoms?
Spock
It's 2^53 (or 2 to the power of 53), same as a conventional C double: http://stackoverflow.com/questions/1848700/biggest-integer-that-can-be-stored-in-a-double
Unless you are talking about a 64bit version of Euphoria, where we use long doubles (80 bits instead of 64bits for a double).
8. Re: bigint/bugnum library
- Posted by jaygade Jul 12, 2013
- 1787 views
Unless you are talking about a 64bit version of Euphoria, where we use long doubles (80 bits instead of 64bits for a double).
For systems where that is an option. (Currently all the systems that EU supports, I think, but it shouldn't be assumed.)
9. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 13, 2013
- 1757 views
Unless you are talking about a 64bit version of Euphoria, where we use long doubles (80 bits instead of 64bits for a double).
For systems where that is an option. (Currently all the systems that EU supports, I think, but it shouldn't be assumed.)
Are there any systems which do not support an 80 bit double? The assumption that an atom is bigger than an integer is pretty fundamental to Euphoria.
10. Re: bigint/bugnum library
- Posted by useless_ Jul 13, 2013
- 1754 views
Out of curiosity, does anyone know the highest integer value at which Eu atoms are still stable for integral amounts. I might have to write a conversion program, which deals with monetary values, for my company and I'd rather avoid having to use a bignum library, if at all possible. A Eu integer maxes out at a billion, right? So if each integral represents one cent the integer would be useful for values up to $10 million. How much higher is the limit using atoms?
Spock
There is another reason to use a bcd math system: it gives the answer that humans expect when they do math.
useless
11. Re: bigint/bugnum library
- Posted by jaygade Jul 13, 2013
- 1787 views
Are there any systems which do not support an 80 bit double? The assumption that an atom is bigger than an integer is pretty fundamental to Euphoria.
ARM
MSVC++ compiler (according to Wikipedia and Microsoft)
I was thinking SPARC and PPC as well, but they are capable of using software 128-bit doubles. So is 64-bit ARM I believe.
For 32-bit Euphoria, 64-bit doubles are the norm, even if they use 80 bits for intermediate results.
12. Re: bigint/bugnum library
- Posted by mattlewis (admin) Jul 13, 2013
- 1719 views
For 32-bit Euphoria, 64-bit doubles are the norm, even if they use 80 bits for intermediate results.
In 32-bit euphoria, 80 bit floating point is never used, except for something serialized as such (presumably from a 64-bit process) or explicit user calls to atom_to_float80 / float80_to_atom.
Matt
13. Re: bigint/bugnum library
- Posted by jaygade Jul 13, 2013
- 1746 views
For 32-bit Euphoria, 64-bit doubles are the norm, even if they use 80 bits for intermediate results.
In 32-bit euphoria, 80 bit floating point is never used, except for something serialized as such (presumably from a 64-bit process) or explicit user calls to atom_to_float80 / float80_to_atom.
Matt
Right, but I believe they're still used for intermediate values on x86 (not in the source, internal to the processor). That's how GCC rolls.
One of the portability changes on my mind is to change the typedef of eudouble to double_t, and then make sure the macros and constants are set according to the value of FLT_EVAL_METHOD in <float.h>. If FLT_EVAL_METHOD == 2 then double_t is defined as long double.
I have not experimented with this yet, and I need to research it further.
14. Re: bigint/bugnum library
- Posted by Spock Jul 13, 2013
- 1785 views
Out of curiosity, does anyone know the highest integer value at which Eu atoms are still stable for integral amounts. I might have to write a conversion program, which deals with monetary values, for my company and I'd rather avoid having to use a bignum library, if at all possible. A Eu integer maxes out at a billion, right? So if each integral represents one cent the integer would be useful for values up to $10 million. How much higher is the limit using atoms?
Spock
It's 2^53 (or 2 to the power of 53), same as a conventional C double: http://stackoverflow.com/questions/1848700/biggest-integer-that-can-be-stored-in-a-double
Thanks [to all] for the reply.
(2 ^53) /100 = 90,071,992,547,409.92 (90 trillion)
To prevent any (digit-based) overflow I should limit the max number of digits which then would give me an upper limit of 10 trillion less one cent.
The highest grossing companies have revenues approaching 1/2 a trillion USD so this method of storing monetary amounts would safely work for any one company, even a massive one, for many years. For our medium size company that limit will never be breached, so my code will never crash. Yay!
Spock
15. Re: bigint/bugnum library
- Posted by mattlewis (admin) Jul 13, 2013
- 1738 views
Thanks [to all] for the reply.
(2 ^53) /100 = 90,071,992,547,409.92 (90 trillion)
To prevent any (digit-based) overflow I should limit the max number of digits which then would give me an upper limit of 10 trillion less one cent.
The highest grossing companies have revenues approaching 1/2 a trillion USD so this method of storing monetary amounts would safely work for any one company, even a massive one, for many years. For our medium size company that limit will never be breached, so my code will never crash. Yay!
When you start running 64-bit euphoria, its integers go up to 262-1, so you'll have plenty of room without even needing floating point.
Matt
16. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 13, 2013
- 1785 views
Not sure this counts, as we can get away with doing it in inline assembly or using machine code.
ARM
I was thinking SPARC and PPC as well, but they are capable of using software 128-bit doubles. So is 64-bit ARM I believe.
Hmm. I guess I thought of ARM as a purely 32bit platform.
I would have thought that all platforms were capable of using 128bit doubles via software emulation, through e.g. http://www.mpfr.org/ (though if we only need 80bit maybe we can find a way to leverage http://gcc.gnu.org/onlinedocs/gccint/Soft-float-library-routines.html )
For 32-bit Euphoria, 64-bit doubles are the norm, even if they use 80 bits for intermediate results.
Right, on 32bit it's largely a non-issue. But on 64bit platforms, we need a floating point type that's bigger than the integer type, as stuff inside the interpreter and runtime library make this assumption, and though it's possible to rewrite the insides to avoid this, it'd probably mean a lot of Euphoria code would also need to be rewritten.
17. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 13, 2013
- 1731 views
(2 ^53) /100 = 90,071,992,547,409.92 (90 trillion)
To prevent any (digit-based) overflow I should limit the max number of digits which then would give me an upper limit of 10 trillion less one cent.
The highest grossing companies have revenues approaching 1/2 a trillion USD so this method of storing monetary amounts would safely work for any one company, even a massive one, for many years. For our medium size company that limit will never be breached, so my code will never crash. Yay!
Spock
Glad to hear that it works for your purposes. Of course, for economists doing calculations on the world economy (something like $60 trillion USD GDP iirc), this isn't enough, so I think we still need a money math lib. A BCD lib would make a lot of sense as well.
18. Re: bigint/bugnum library
- Posted by jaygade Jul 13, 2013
- 1725 views
Right, on 32bit it's largely a non-issue. But on 64bit platforms, we need a floating point type that's bigger than the integer type, as stuff inside the interpreter and runtime library make this assumption, and though it's possible to rewrite the insides to avoid this, it'd probably mean a lot of Euphoria code would also need to be rewritten.
The real portability/compatibility problem comes from 32 vs 64 bit integers, instead of defining Euphoria integers as definitely one or the other.
THAT's where the biggest incompatibility will be. If we say that Euphoria integers are AT LEAST 64 bits (a performance issue only on 32-bit machines) then we should be okay. But if we say that integers are 32 or 53 bits on 32 bit machines, but 63 bits or 64 bits on a 64 bit machine, then we may have problems.
19. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 13, 2013
- 1752 views
Right, on 32bit it's largely a non-issue. But on 64bit platforms, we need a floating point type that's bigger than the integer type, as stuff inside the interpreter and runtime library make this assumption, and though it's possible to rewrite the insides to avoid this, it'd probably mean a lot of Euphoria code would also need to be rewritten.
The real portability/compatibility problem comes from 32 vs 64 bit integers, instead of defining Euphoria integers as definitely one or the other.
I agree that this is a real portability/compatibility problem.
THAT's where the biggest incompatibility will be.
The way 4.1 is right now, I would agree. If we allow atoms to be smaller than integers, then I believe that this would become a bigger incompatibility - and having both would certainly make things no easier for anyone.
If we say that Euphoria integers are AT LEAST 64 bits (a performance issue only on 32-bit machines) then we should be okay.
Hmm. I confess that I really like the idea of having 64bit sized integers and 80bit atoms on 32bit 4.1 Euphoria. (Though this combination is not possible on ARM without some software emulation, as you pointed out.)
But if we say that integers are 32 or 53 bits on 32 bit machines, but 63 bits or 64 bits on a 64 bit machine, then we may have problems.
Future code can be ifdef'd to deal with this when necessary. I guess the big issue is porting existing code.
Aside from math libraries and low level code (e.g. the interface to C libraries), I was hoping that most code wouldn't care about the underlying size of an integer or an atom. But I can see this come back to bite us when we least expect it...
20. Re: bigint/bugnum library
- Posted by mattlewis (admin) Jul 13, 2013
- 1731 views
Glad to hear that it works for your purposes. Of course, for economists doing calculations on the world economy (something like $60 trillion USD GDP iirc), this isn't enough, so I think we still need a money math lib. A BCD lib would make a lot of sense as well.
Those guys wouldn't care about cents or even thousands of dollars, though. But definitely don't code for Zimbabwe.
Matt
21. Re: bigint/bugnum library
- Posted by mattlewis (admin) Jul 13, 2013
- 1723 views
If we say that Euphoria integers are AT LEAST 64 bits (a performance issue only on 32-bit machines) then we should be okay.
Hmm. I confess that I really like the idea of having 64bit sized integers and 80bit atoms on 32bit 4.1 Euphoria. (Though this combination is not possible on ARM without some software emulation, as you pointed out.)
Ugh. I really don't like this idea.
Matt
22. Re: bigint/bugnum library
- Posted by jaygade Jul 13, 2013
- 1771 views
The way 4.1 is right now, I would agree. If we allow atoms to be smaller than integers, then I believe that this would become a bigger incompatibility - and having both would certainly make things no easier for anyone.
I don't think that would be as big of an issue, really. Atoms can still be larger than integers, it's just that they won't be as accurate for pure integer values.
Even double atoms can still be +/- 1e37. That's WAY bigger than most machine integers. And long doubles are +/-1e307 I think? That is HUGE.
If we say that Euphoria integers are AT LEAST 64 bits (a performance issue only on 32-bit machines) then we should be okay.
Hmm. I confess that I really like the idea of having 64bit sized integers and 80bit atoms on 32bit 4.1 Euphoria. (Though this combination is not possible on ARM without some software emulation, as you pointed out.)
80-bits is good, but we shouldn't rely on it. I'm actually suggesting that maybe on 32-bit Euphoria, integers should be up to 63-bits. We can rely on that for all 32-bit implementations, I believe, with a little extra code.
But if we say that integers are 32 or 53 bits on 32 bit machines, but 63 bits or 64 bits on a 64 bit machine, then we may have problems.
Future code can be ifdef'd to deal with this when necessary. I guess the big issue is porting existing code.
We shouldn't have to ifdef much, if anything, unless existing code relied on larger ranges. Most older code relies on smaller ranges so it shouldn't be an issue.
Aside from math libraries and low level code (e.g. the interface to C libraries), I was hoping that most code wouldn't care about the underlying size of an integer or an atom. But I can see this come back to bite us when we least expect it...
I agree 100%. The Euphoria user should not have to worry about differences in underlying sizes within reason, which 80+ -bit long doubles and 63-bit integers should provide. There should be one set of limits for integers regardless of the underlying architecture, and we should advise users that limits on atoms might apply if they have a certain class of processor.
Note: None of this means that we don't need an arbitrary-precision library, because that would be useful.
23. Re: bigint/bugnum library
- Posted by jaygade Jul 13, 2013
- 1701 views
Ugh. I really don't like this idea.
Matt
Which part of the idea, and why?
24. Re: bigint/bugnum library
- Posted by mattlewis (admin) Jul 13, 2013
- 1746 views
Ugh. I really don't like this idea.
Matt
Which part of the idea, and why?
It's likely a performance disaster for 32-bit code, for one, and it probably breaks a lot of 32-bit code. There are a few portability issues, but it's not really any worse than accidentally using an integer for a pointer in current 32-bit code.
Matt
25. Re: bigint/bugnum library
- Posted by jimcbrown (admin) Jul 13, 2013
- 1752 views
The way 4.1 is right now, I would agree. If we allow atoms to be smaller than integers, then I believe that this would become a bigger incompatibility - and having both would certainly make things no easier for anyone.
I don't think that would be as big of an issue, really. Atoms can still be larger than integers, it's just that they won't be as accurate for pure integer values.
Even double atoms can still be +/- 1e37. That's WAY bigger than most machine integers. And long doubles are +/-1e307 I think? That is HUGE.
Actually, this was a major headache and the reason I never finished my 64bit port - all kinds of weird problems showed up when this assumption is broken.
Matt did it, but once he had the proof of concept he decided things would be easier as well for an atom to be able to hold all the integral values that the integer type can hold.
If we say that Euphoria integers are AT LEAST 64 bits (a performance issue only on 32-bit machines) then we should be okay.
Hmm. I confess that I really like the idea of having 64bit sized integers and 80bit atoms on 32bit 4.1 Euphoria. (Though this combination is not possible on ARM without some software emulation, as you pointed out.)
80-bits is good, but we shouldn't rely on it. I'm actually suggesting that maybe on 32-bit Euphoria, integers should be up to 63-bits. We can rely on that for all 32-bit implementations, I believe, with a little extra code.
I'm skeptical, because of the above.
Note: None of this means that we don't need an arbitrary-precision library, because that would be useful.
Seconded.
If we say that Euphoria integers are AT LEAST 64 bits (a performance issue only on 32-bit machines) then we should be okay.
Hmm. I confess that I really like the idea of having 64bit sized integers and 80bit atoms on 32bit 4.1 Euphoria. (Though this combination is not possible on ARM without some software emulation, as you pointed out.)
Ugh. I really don't like this idea.
Matt
Seconded (at least in the ARM case, and it'd certainly be nice if we were consistent across all 32bit platfors).
26. Re: bigint/bugnum library
- Posted by mattlewis (admin) Jul 13, 2013
- 1729 views
Actually, this was a major headache and the reason I never finished my 64bit port - all kinds of weird problems showed up when this assumption is broken.
Matt did it, but once he had the proof of concept he decided things would be easier as well for an atom to be able to hold all the integral values that the integer type can hold.
The problem comes from detecting when an integer should be promoted to a double, internally. As noted, you start losing granularity after 253-1 with a normal double. We could have made 64-bit integers be smaller than that, but that didn't seem like a great idea.
Matt
27. Re: bigint/bugnum library
- Posted by jaygade Jul 13, 2013
- 1747 views
The way 4.1 is right now, I would agree. If we allow atoms to be smaller than integers, then I believe that this would become a bigger incompatibility - and having both would certainly make things no easier for anyone.
I don't think that would be as big of an issue, really. Atoms can still be larger than integers, it's just that they won't be as accurate for pure integer values.
Even double atoms can still be +/- 1e37. That's WAY bigger than most machine integers. And long doubles are +/-1e307 I think? That is HUGE.
Actually, this was a major headache and the reason I never finished my 64bit port - all kinds of weird problems showed up when this assumption is broken.
Matt did it, but once he had the proof of concept he decided things would be easier as well for an atom to be able to hold all the integral values that the integer type can hold.
It's STILL a headache, actually. Or so I've found when trying to port to OS X. I'm STILL obsessed with getting it right. (At least I'm not getting any more segfaults).
28. Re: bigint/bugnum library
- Posted by bugmagnet Jul 18, 2013
- 1686 views
Just to let you know, I've released some code on eu-bignum for integer bignums. My javascript port (js-bignum) is well advanced with the beginnings of an ersatz floating point support. This will get migrated back to the euphoria code in due course.
Bugmagnet
29. Re: bigint/bugnum library
- Posted by bugmagnet Jul 18, 2013
- 1720 views
text.ex demonstrates calculating 2^1000. The library uses memoization so the calculation is pretty fast.
Bugmagnet
