Re: BIGNUM memory and questions

>>>>> "T" == Tels  <[email protected]> writes:

  T> Yes. My reason was: "Choose wisely which way you use." And currently I
  T> didn't get the impression that the decisions were wisely, they looked
  T> rather arbitrarily.

i am not choosing arbitrarily. please stop saying that. if you want to
write a competing version go ahead. just email dan first and get his ok.

  T> Can I see the specs? I still am unsure what this entire thing is for, I got
  T> the vague impression it is for Perl6 bignum handling, which is why I take
  T> so much interest.

it is for parrot bignum handline which will be for perl6.

  T> A bignum interface for perl6 which can only do *+-/% isn't very complete.
  T> And if you need to emulate the missing things (like sqrt()) in Perl6, you
  T> are where you are with use Math::Bigint lib => 'Pari'; slow speed for
  T> some things, and fast for others.

dan agreed that all we need to do initially are the basic operations. if
someone wants transcendental functions and whatever, then regular floats
are best for speed. 

  T> You can, at least generally. Thats the trick about thinking before
  T> rushing to the code. You can, f.i. find out whether your operations
  T> will be O(N*N) or O(N) or (1). And this is important when the
  T> numbers become really big. An algorithmn which takes O(N*N) will be
  T> slower from some point than one with O(N), no matter how fast the
  T> first handles the small cases.

addition is still O(N) in bcd and multiplication will be no worse order
than a binary form. i have cache ideas that will speed up large
multiplications to where they may even be faster then simple binary
forms. only a benchmark will tell.

  T> It is all about finding out whether you can take the performance hit for
  T> small cases and make the big cases fast, or want fast small numbers and
  T> slow big numbers.

  T> One example:

  T>         use Math::BigInt;
  T>         $x = 2 << 654321;

  T> This will be slow in Calc/BCD. 

and it won't be directly supported anyhow. that is not a goal.

  T> F.i., one important point is whether to store the numbers in reduced
  T> (1e1000 vs 1000000..000) form or not. When you store them in reduced form,
  T> you can not easily switch from BCD to binary, because in binary it is
  T> impossible to know how many zeros there are. You have to convert to dec to
  T> look. But that means that _every_ operation that changes and then reduces
  T> the number (typical every operation that changes the number) becomes
  T> O(N*N), even simple add/inc operations. (This is, f.i. a problem of the
  T> current way Math::BigFloat handles it's numbers).

one other aspect of this design is a fixed precision for a given
bignum. it can be changed or allowed to grow as needed but the default
is some fixed number of digits. this is to make 1/3 work without sucking
up all of ram. numbers will be normalized to that precision and an
exponent will handle extra scaling.

  T> So, declaring that "we store the numbers in 1exx form to save some memory"
  T> is a dangerous thing when you don't now about the consequences.

not if that is specified in advance. and you can change the precision as
needed with method calls on the bignum. (i assume that will be done in
the perl6 language specs).

  T> One of the problems here is that optimize beforehand for certain things,
  T> like fast string conversation. Unfortunately, not everyone needs this, if
  T> you want, f.i. do RSA, string conversation doesn't worry you, but fast
  T> multiply, power and mod operations do. If you as a user, can't switch the
  T> math under the hood, you are stuck with something slow.

  >> It's apples and oranges anyway, since BigInt doesn't do fractions.

  T> BigFloats do. (And they represent integers at the same time)

does it do accurate decimal fractions? 

  T> Anyway, I currently don't see how I can bring anything usefull to
  T> you, since all decsions seem already be made. So I stop now. If you
  T> or anyone has ever any questions, please email me.

you don't get it. nothing is in concrete. i am proposing a design and
working (slowly) on the code. all on this list are invited to work on
it. you seem to have predetermined choice of the existing perl4(!)  math
libraries because of your vested work in them. they are not appropriate
for parrot as they are not in c. they won't be as fast as even a bcd
version in c. there can be no perl code inside a running parrot
engine. parrot runs perl code but is not written IN perl.

if you want to help with this design, feel free. but stop with the
negative comments like i don't know anything and my choices are
arbitrary. bcd has its benefits and this is a design with fixed
precision support, integer and floats, and the basic math. dan has
okayed it as long as it has decent performance (note that maximum
performance is NOT a spec), and it is pluggable. 

uri

-- 
Uri Guttman  ------  [email protected]  -------- http://www.stemsystems.com
-- Stem is an Open Source Network Development Toolkit and Application Suite -
----- Stem and Perl Development, Systems Architecture, Design and Coding ----
Search or Offer Perl Jobs  ----------------------------  http://jobs.perl.org