Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2012-08-29 21:49:27

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Spigot algorithms and log(2)

Hi;

How can we use a spigot algorithm to calculate the digits of a constant? I will use the Wikipedia article and flesh out the explanation a bit so that we can see it used on a real problem.

Let's see if we can get the 50th binary digit of log(2). We will use the relation:

First we multiply both sides of 1) by 2^49.

The RHS is split into two parts.

This term on the right is the important one.

We can replace 4) with

This form can be rapidly computed using mods and only needs floating point arithmetic of the single precision variety. So 3) becomes:


Okay, let's do the number crunching and let's try to get it right.

We are only interested in the fractional part so this becomes,

( You may have noticed the smearing error in the above calculation and how to repair it.)

Now we need that number in binary.

So according to our calculations the 50th - 56th binary digit of log(2) is 1111001

Checking this we find that we have agreement between our prediction in 7) and the answer from the 50th to the 56th digit.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#2 2012-08-30 00:37:08

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Spigot algorithms and log(2)

Hi bobbym

Could you explain how you got from 4) to 5) ?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#3 2012-08-30 04:48:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Spigot algorithms and log(2)

Hi;

To say you get from 4 to 5 is a misconception. Try

and

then see what you get.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB