Front page | perl.perl6.internals.bignum |
Postings from November 2001
Re: BIGNUM memory and questions
November 27, 2001 23:47
Re: BIGNUM memory and questions
Message ID: firstname.lastname@example.org
-----BEGIN PGP SIGNED MESSAGE-----
On 27-Nov-01 John M. Gamble tried to scribble about:
> On Tue, 27 Nov 2001, Tels wrote:
>> On 27-Nov-01 Uri Guttman tried to scribble about:
>> > T> Next question: Why BCD? Do you think this is better, or do you
>> > T> know? (E.g. why was that decision made. I am asking because
>> > there
>> > T> are differences and I want to make sure that the decision is done
>> > T> on research, not on "Uh, we thought it would be better" ;)
>> > bcd is more accurate which is a prime reason.
>> This is untrue. Neither binary nor BCD are more or less accurare.
>> Math::BigInt lib => 'Pari' would not work 100% as Math::BigInt;
> The BCD form is handling fractional parts too, hence the accuracy
use Math::BigInt lib => 'Pari;
drives Math::Bigint with Pari, a binary package. And Math::BigFloat simple
uses BigInt to represent fractions, too. Again, there is no loss of
accuracy (the lib => Pari is optional, it does change the speed, not the
accuracy). It all depends on how you present the things.
> I personally am taking a great interest in this, which is why i
> to help. About a decade ago, i wrote a VLI package in C++ (which no
> compiles in current C++ packages, alas), so i know that these things can
> be done in multiple ways.
Yes. My reason was: "Choose wisely which way you use." And currently I
didn't get the impression that the decisions were wisely, they looked
> I don't think we have to worry about backwards
> compatibility as long as we keep the interface simple - strings,
> integers, and reals to internal format, and back again.
Can I see the specs? I still am unsure what this entire thing is for, I got
the vague impression it is for Perl6 bignum handling, which is why I take
so much interest.
A bignum interface for perl6 which can only do *+-/% isn't very complete.
And if you need to emulate the missing things (like sqrt()) in Perl6, you
are where you are with use Math::Bigint lib => 'Pari'; slow speed for
some things, and fast for others.
>> > it will allow for easier conversions to/from strings.
>> This is true. But it will make for very slow multiplications and things
>> like 2 ** something. (I bet you know that ;)
> Not necessarily. There are tricks out there for BCD math too. I admit
> you won't get the instant bit set with the '<<' and '>>' operators
> are those operators part of the spec?), but 'natural' multiplication
> shouldn't be too much slower. Remember, we're dealing with reals also.
>> It will be _MUCH_ slower for some cases. Heh, want some benchmarks? ;)
> We'll have to benchmark anyway. Come on, we can't make speed claims in
> advance of the the code's existance!
You can, at least generally. Thats the trick about thinking before
rushing to the code. You can, f.i. find out whether your operations will be
O(N*N) or O(N) or (1). And this is important when the numbers become really
big. An algorithmn which takes O(N*N) will be slower from some point than
one with O(N), no matter how fast the first handles the small cases.
It is all about finding out whether you can take the performance hit for
small cases and make the big cases fast, or want fast small numbers and
slow big numbers.
$x = 2 << 654321;
This will be slow in Calc/BCD.
use Math::BigInt lib => 'Pari';
$x = 2 << 654321;
This will be fast. But print "$x\n"; will be faster in the first case, and
slower in the second case.
It is important to decide about these things either beforehand, or plan
them to be changable.
F.i., one important point is whether to store the numbers in reduced
(1e1000 vs 1000000..000) form or not. When you store them in reduced form,
you can not easily switch from BCD to binary, because in binary it is
impossible to know how many zeros there are. You have to convert to dec to
look. But that means that _every_ operation that changes and then reduces
the number (typical every operation that changes the number) becomes
O(N*N), even simple add/inc operations. (This is, f.i. a problem of the
current way Math::BigFloat handles it's numbers).
So, declaring that "we store the numbers in 1exx form to save some memory"
is a dangerous thing when you don't now about the consequences.
One of the problems here is that optimize beforehand for certain things,
like fast string conversation. Unfortunately, not everyone needs this, if
you want, f.i. do RSA, string conversation doesn't worry you, but fast
multiply, power and mod operations do. If you as a user, can't switch the
math under the hood, you are stuck with something slow.
> It's apples and oranges anyway, since BigInt doesn't do fractions.
BigFloats do. (And they represent integers at the same time)
[remaining comments snipped].
Anyway, I currently don't see how I can bring anything usefull to you,
since all decsions seem already be made. So I stop now. If you or anyone
has ever any questions, please email me.
perl -MDev::Bollocks -e'print Dev::Bollocks->rand(),"\n"'
advantageously network fifth-generation e-tailers
http://bloodgate.com/perl My current Perl projects
PGP key available on http://bloodgate.com/tels.asc or via email
-----BEGIN PGP SIGNATURE-----
-----END PGP SIGNATURE-----