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

* 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! :-)).


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: 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: Any progress yet? (was Re: Fast pi program?)
    ... conversion to base 26, ... Base 2^32 would /reduce/ the number of digits by a factor of about 1.7 ... numbers approximated with floating point is even worse.), the "pyramid ... it does cancel the performance gain if there was any. ...
    (comp.programming)
  • 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: %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)