Re: computing fractions

On Wed, 30 May 2007 10:48:21 +0200, Blod-Svente wrote:

A really basic math question:

I'm trying to compute values like 2^-30000 (in base 10 representation).
I'd like to get the decimals directly, without dividing
a bignum 40000 times to get 2^-40000 etc.

There oughta be some smarter way? (Say, O(log N) rather than O(N)...)
A general method (for any number base) would be cool, but I'm also
all ears if there's some special method for power of 2 fractions.

The right terminology so I can find it with google/wikipedia may be all I need...

Thanks,

Bosse
You can compute b^n in around log2(n) multiplies:
power( b, n)
if n == 0 return 1;
if n == 1 return b;
t = power(b*b, n/2); /* integer division! */
if odd(n) t *= b;
return t;

(You could use a similar method base 4, but the savings are tiny,
around 1% for n up to 100000)
Duncan

.

Relevant Pages

  • computing fractions
    ... I'm trying to compute values like 2^-30000 (in base 10 representation). ... I'd like to get the decimals directly, without dividing ... a bignum 40000 times to get 2^-40000 etc. ... A general method would be cool, ...
    (comp.programming)
  • Re: computing fractions
    ... CBFalconer wrote: ... representation). ... dividing a bignum 40000 times to get 2^-40000 etc. ...
    (comp.programming)
  • Re: 5 worst SCOTUS decisions (post WW2)
    ... The issue involved how much power state A would have ... compared to the of four districts each with 1 million. ... "It would defeat the principle solemnly embodied in the Great Compromise - equal representation in the House for equal numbers of people - for us to hold that, within the States, legislatures may draw the lines of congressional districts in such a way as to give some voters a greater voice in choosing a Congressman than others." ... it's no surprise that the constitution did not mandate that they do. ...
    (rec.sport.football.college)
  • Re: On Talking to the USFS
    ... You have the power to resist. ... their group and acquescing to their representation of me. ... You have to quit believing them Federales. ... a right by complying with its annulment. ...
    (alt.gathering.rainbow)
  • Re: On Talking to the USFS
    ... You have the power to resist. ... their group and acquescing to their representation of me. ... course of action I can take that avoids accepting Plunker/Garrick et ... situations I could see a clear path through the court system and did ...
    (alt.gathering.rainbow)