Various Topics on Programming

..k..

On Jun 15, 3:33 pm, lawrence.jo...@ugs.com wrote:
> mike3 <mike4...@yahoo.com> wrote:
>
> > So, overall, in a toss-off between base 2 and base 4294967296, which
> > is best?
>
> So, overall, in a toss-off between a Mack Truck and a Volkswagen Beetle,
> which is best?
>

Well, I want speed -- that's what I'm aiming for, and it needs to be
reasonably
fast for both small (64 bit minimum) and large (8192 bit maximum)
numbers,
on all four arithmetic operations (+, -, *, /).

> -Larry Jones
>
> Nobody knows how to pamper like a Mom. -- Calvin

..bertwesse.. ..hoo.c..

On Jun 15, 2:17 pm, mike3 <mike4...@yahoo.com> wrote:
> > As always, it depends on your application. If you're dealing with
> > more than about three words of precision in software, it's almost
> > certainly worth it from a performance perspective to make the base the
> > word size and take the hit of adding an extra word to deal with the
> > wobble. Size consideration on shorter number may make you go the
> > other direction.
>
> I need to handle both (min. 64 bits, max. 8192 bits, all with a 32-bit
> word size (so that's 2 words all the way up to 256 words.)). Speed
> is the primary concern here.


Many bignum libraries take different code paths for various operations
depending on the size of the operands, and that would certainly be an
option (IOW, one path for two short format numbers, one for two long,
and one for a mix - although I don't know of anyone who's taken that
approach with different *formats*). But I suspect the gains from a
format change will be modest at the two-three word end of the range
(and you really will need to test that), so unless you really need
that last big of performance for short numbers, I'd just stick with
the base 2**32 format and add an extra word.

And is there some reason you're not using GMP? You're highly unlikely
to be able to invest enough time to beat their existing performance.
If speed is the primary concern, then doing this yourself is clearly
the wrong approach, since the GMP crew has spent years optimizing
performance.

There are other bignum libraries out there, but most limit themselves
to integer operations, so those might be useful as a base to build on,
but GMP does have big-float (unlimited mantissa size, although the
exponent is limited to a word). At the very least you should look at
their code.

..k..

On Jun 15, 4:40 pm, "robertwess...@yahoo.com"
<robertwess...@yahoo.com> wrote:
> On Jun 15, 2:17 pm, mike3 <mike4...@yahoo.com> wrote:
>
> > > As always, it depends on your application. If you're dealing with
> > > more than about three words of precision in software, it's almost
> > > certainly worth it from a performance perspective to make the base the
> > > word size and take the hit of adding an extra word to deal with the
> > > wobble. Size consideration on shorter number may make you go the
> > > other direction.
>
> > I need to handle both (min. 64 bits, max. 8192 bits, all with a 32-bit
> > word size (so that's 2 words all the way up to 256 words.)). Speed
> > is the primary concern here.
>
> Many bignum libraries take different code paths for various operations
> depending on the size of the operands, and that would certainly be an
> option (IOW, one path for two short format numbers, one for two long,
> and one for a mix - although I don't know of anyone who's taken that
> approach with different *formats*). But I suspect the gains from a
> format change will be modest at the two-three word end of the range
> (and you really will need to test that), so unless you really need
> that last big of performance for short numbers, I'd just stick with
> the base 2**32 format and add an extra word.
>

I would doubt I'd need the extra performance on the small nums -- in
fact with a few tests I did the penalty wasn't as bad as I worried it
would be. And anything below 64 bits of precision is best handled with
preexisting floating point hardware arithmetic (doubles).

> And is there some reason you're not using GMP? You're highly unlikely
> to be able to invest enough time to beat their existing performance.
> If speed is the primary concern, then doing this yourself is clearly
> the wrong approach, since the GMP crew has spent years optimizing
> performance.
>

Well, for one I do not need to _beat_ GMP. There's a certain point at
which further optimization yields diminishing returns -- you can only
go so fast and trying to push the envelope at that point just becomes
more of an obsession then a necessity (This is not, I repeat, NOT a
race -- it does not have to be the fastest thing on the planet, it
just has to be fast enough the user won't be turned off by it's
slowness, ie. fast enough it's easy to use, not neessarily a top-of-
the-line "race car".). Furthermore, GMP is a general purpose system,
designed for all sorts of uses, instead of one specific program, ie.
bloated.

Plus, it's a challenge, too. And why couldn't I invest enough time to
get it to said "fairly good" level of performance?


> There are other bignum libraries out there, but most limit themselves
> to integer operations, so those might be useful as a base to build on,
> but GMP does have big-float (unlimited mantissa size, although the
> exponent is limited to a word). At the very least you should look at
> their code.

I actually *have* looked through GMP's code, by the way, and guess
what -- it uses base 2^32 (or whatever the word size is on the
machine). Yep, you read that right. Mmm-hmm. If it's good enough for
GMP, it's probably good enough for my program, too. I haven't heard
anyone complaining about GMP's use of it.