Re: Any progress yet? (was Re: Fast pi program?)

On Aug 31, 12:43 am, "Alf P. Steinbach" <al...@xxxxxxxx> wrote:
* mike3:

On Aug 30, 11:49 pm, "Alf P. Steinbach" <al...@xxxxxxxx> wrote:

I'd had to really delve into this to give specific advice (and Things Take Time).
For now, looking only at the [pib26.c] main program source, it seems the
program is actually /calculating/ in base 26^4. Perhaps that's a choice
found after measuring the cost of calculating in a binary base and then
converting to base 26, or perhaps it's not? If number system conversion
requires quadratic time (does it?) perhaps this is best, but if not,
perhaps a change to internal binary system computation, with final
conversion to base 26, would really speed things up? Just a wild guess.

It does calculate in base 26^4. You are right. To compute in base 10
you need to compute 2x the digits then convert to 26 (since the
algorithms work best with powers of 2 numeric sizes),

Uh, no, I suggested a binary base. In particular, e.g. base 2^32, or,
since it seems the program is doing 64-bit calculations, base 2^64.

Base 2^32 would /reduce/ the number of digits by a factor of about 1.7
compared to base 26^4; base 2^64 would reduce the number of digits by
twice that; and both would perhaps (I don't know) also avoid costly
per-digit remainder operations in all arbitrary precision operations.

But as I wrote quoted above, I don't know the cost of the final radix
conversion (I suspect it would take seconds to google but that's your
work! :-)).


Sorry but that won't do either. At base 2^32 the "multiplication
pyramid"
overflows very easily. If you pack 4 elements and you use 8 primes
for the modulo math in the NTT (FFT done in a finite field. The
complex
numbers approximated with floating point is even worse.), the "pyramid
size" goes up to like 256 bits, but the primes only handle around 248
or so. You'd have to use some "weird" base that doesn't fit nice on
byte boundaries and that just makes the programming worse (shifts
and masks start appearing in add/sub routines, etc.).

You can use the following formula to determine how many bits
the FFT must be capable of representing:

Pyramid Size = lg(nine^2) + lg(FFT Size)

Here, "nine = base - 1", so-named since 9 = 10-1.

If we want to pack 1 digit per prime (otherwise we start to
decrease the effective base) the effective Base = base^8,
so then we have lg(base^16) in there approximately. That
limits us to lg(base^16) + lg(FFT Size). With FFT Size = 16777216,
and Pyramid Size = 248, the base is

Base = sixteenth root(2^(Pyramid Size - lg(FFT Size)))
= sixteenth root(2^(248 - 24))
= sixteenth root(2^224)
= 2^(224/16)
= 2^14
= 16,384.

If we pack only numprimes/2 = 4 like we do with base 456,976
then the maximum base goes to

Base = eighth root(2^224)
= 2^(224/8)
= 2^28
= 268435456.

That's not much better than 5 base 26 digits per element. (it's
between 5 and 6). Not much of a gain.

So yes, it does cancel the performance gain if there was any.

which
effectively cancels much of the speed gain.

Nope, see above.

Plus that final
radix conversion is _not_ cheap, you know.

Well I don't know. Could be worth checking. Yes?

Cheers, & hth.,

- Alf

PS: Please don't quote signatures.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?


.

Relevant Pages

  • Re: Any progress yet? (was Re: Fast pi program?)
    ... conversion to base 26, ... you need to compute 2x the digits then convert to 26 (since the ... If you pack 4 elements and you use 8 primes ... numbers approximated with floating point is even worse.), the "pyramid ...
    (comp.programming)
  • Re: How to get decimal form of largest known prime?
    ... but I learned from it much about Python syntax. ... here code of a bigDecReprOfInt class as a kind of module and ... i.e. 4096 and not as I would expect it 80 decimal digits long ... # and strconversion for very large integers i. ...
    (comp.lang.python)
  • Re: %x question
    ... %x is a conversion specifier that makes any of the printf ... the letters abcdef are used for x conversion and the letters ... fewer digits, it is expanded with leading zeros. ... The result of converting a zero value with a precision of zero is ...
    (comp.lang.c)
  • Re: Singles to Doubles
    ... I'm guessing that VB calculates its Singles and Doubles using some kind of power series expansion... ... Now, to continue my guessing, I think 15 digits were calculated for the Single and stored; but, because VB knows it is a Single, it only reports 6 of 7 digits when asked. ... Now, for the CStr conversion, I think VB is grabbing only the 6 or 7 digits it would normally use for display. ...
    (microsoft.public.vb.general.discussion)
  • Re: Enigma 1456 - Cutting edge
    ... ACD* and the other through the plane A*C*D. ... volume of that pyramid is p^2 q / 6. ... in that number each of the two digits ... p^2 q being an integer multiple of 24. ...
    (rec.puzzles)
Loading