Group Abstract Group Abstract

Message Boards Message Boards

Formula for computing sqrt(2) of binary numbers

Attachments:
POSTED BY: Mariusz Iwaniuk
14 Replies

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: EDITORIAL BOARD
POSTED BY: Simon Plouffe
POSTED BY: Mariusz Iwaniuk

Finding formula for the n-th digit in the binary representation of Sqrt[2] using Floor function.

 sol = RSolve[{b[n + 2] == a[n + 1] - 2*a[n], a[n] == Floor[Sqrt[2]*2^n], b[0] == 1, b[1] == 0}, {b[n], a[n]}, n]
 sol2 = FullSimplify[b[n] /. sol[[1]], Assumptions -> {n > 0, n \[Element] Integers}]

$$B_n=-2 \left\lfloor 2^{-\frac{3}{2}+n}\right\rfloor +\left\lfloor 2^{-\frac{1}{2}+n}\right\rfloor$$

This is formula for the n-th digit in the binary representation of $\sqrt{2}$ for $n > 0$ and $n\in \mathbb{Z}$ using Floor function.

 Table[sol22 /. n -> m, {m, 1, 50}] 

$ {1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, \ 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, \ 1, 0, 0, 1} $

POSTED BY: Mariusz Iwaniuk

Just checking: is this, then, some kind of spigot algorithm for sqrt(2)?

https://en.wikipedia.org/wiki/Spigot_algorithm

POSTED BY: Sander Huisman

No is not algorithm, it's better than that. It simple, it's a formula, or function.

An example:

To start calculating binary digits from, say, the 8th place only need substitute for n=8,9,10,11,12,13,14,15....That it's all.

formula =1/2 - (2 ArcTan[Cot[2^(-(3/2) + n) \[Pi]]])/\[Pi] + ArcTan[Cot[2^(-(1/2) + n) \[Pi]]]/\[Pi]

sol = Table[formula, {n, 8, 15}] // N // Round

${1, 0, 0, 0, 0, 0, 1, 0}$

and say from n=1....15:

 sol2 = Table[formula, {n, 1, 15}] // N // Round

${1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0}$

POSTED BY: Mariusz Iwaniuk
POSTED BY: Sander Huisman
POSTED BY: Mariusz Iwaniuk

Appendix: To simplify $B_n$ formula.

We have: $$B_n=\frac{i \left(-i \pi +2 \log \left(1-e^{-i 2^{-\frac{1}{2}+n} \pi }\right)-2 \log \left(1-e^{i 2^{-\frac{1}{2}+n} \pi }\right)-\log \left(1-e^{-i 2^{\frac{1}{2}+n} \pi }\right)+\log \left(1-e^{i 2^{\frac{1}{2}+n} \pi }\right)\right)}{2 \pi }$$

 sol2 = (I (-I \[Pi] + 2 Log[1 - E^(-I 2^(-(1/2) + n) \[Pi])] - 2 Log[1 - E^(I 2^(-(1/2) + n) \[Pi])] - Log[1 - E^(-I 2^(1/2 + n) \[Pi])] +  Log[1 - E^(I 2^(1/2 + n) \[Pi])]))/(2 \[Pi])
 sol5 = FullSimplify[Re[sol2] // ComplexExpand, Assumptions -> n \[Element] Integers]
 Table[sol5, {n, 1, 5}]

$\left\{\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(\sqrt{2} \pi \right)}{1-\cos \left(\sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(2 \sqrt{2} \pi \right)}{1-\cos \left(2 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(2 \sqrt{2} \pi \right)}{1-\cos \left(2 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(4 \sqrt{2} \pi \right)}{1-\cos \left(4 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(4 \sqrt{2} \pi \right)}{1-\cos \left(4 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(8 \sqrt{2} \pi \right)}{1-\cos \left(8 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(8 \sqrt{2} \pi \right)}{1-\cos \left(8 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(16 \sqrt{2} \pi \right)}{1-\cos \left(16 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(16 \sqrt{2} \pi \right)}{1-\cos \left(16 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(32 \sqrt{2} \pi \right)}{1-\cos \left(32 \sqrt{2} \pi \right)}\right)}{2 \pi }\right\}$

Now we need find a pattern.The first ingredient in the formula: We have: $$\left\{4 \tan ^{-1}\left(\frac{\sin \left(\sqrt{2} \pi \right)}{1-\cos \left(\sqrt{2} \pi \right)}\right),4 \tan ^{-1}\left(\frac{\sin \left(2 \sqrt{2} \pi \right)}{1-\cos \left(2 \sqrt{2} \pi \right)}\right),4 \tan ^{-1}\left(\frac{\sin \left(4 \sqrt{2} \pi \right)}{1-\cos \left(4 \sqrt{2} \pi \right)}\right),4 \tan ^{-1}\left(\frac{\sin \left(8 \sqrt{2} \pi \right)}{1-\cos \left(8 \sqrt{2} \pi \right)}\right),\tan ^{-1}\left(\frac{\sin \left(16 \sqrt{2} \pi \right)}{1-\cos \left(16 \sqrt{2} \pi \right)}\right)\right\}$$

 FindSequenceFunction[{1, 2, 4, 8, 16}, n]
 (*2^(-1 + n)*)

Finding the second ingredient in the formula is the same how I found at first:

 FindSequenceFunction[{2, 4, 8, 16, 32}, n]
 (*2^n*)

Substitution:

$$\frac{\pi -\left(4 \tan ^{-1}\left(\frac{\sin \left(n \sqrt{2} \pi \right)}{1-\cos \left(n \sqrt{2} \pi \right)}\right)\text{/.}\, n\to 2^{n-1}\right)+\left(2 \tan ^{-1}\left(\frac{\sin \left(n \sqrt{2} \pi \right)}{1-\cos \left(n \sqrt{2} \pi \right)}\right)\text{/.}\, n\to 2^n\right)}{2 \pi }$$

  FullSimplify[(\[Pi] - (4 ArcTan[Sin[n Sqrt[2] \[Pi]]/(1 - Cos[n Sqrt[2] \[Pi]])] /. n -> 2^(n - 1)) + (2 ArcTan[Sin[n Sqrt[2] \[Pi]]/(
  1 - Cos[n Sqrt[2] \[Pi]])] /. n -> 2^n))/(2 \[Pi])] // Expand

$$B_n = \frac{1}{2}-\frac{2 \tan ^{-1}\left(\cot \left(2^{-\frac{3}{2}+n} \pi \right)\right)}{\pi }+\frac{\tan ^{-1}\left(\cot \left(2^{-\frac{1}{2}+n} \pi \right)\right)}{\pi }$$

POSTED BY: Mariusz Iwaniuk

Neat! Is it your result and is it new? Do you think expression can be simplified? This does not work

$$\arctan{u}+\arctan{v}=\arctan\left(\frac{u+v}{1-uv}\right)$$

but maybe similar trigonometry.

POSTED BY: Sam Carrettie

Yes, I found this formula.Is it new? Probably so. I searched in the web, but did not find a similar formula.

I tried to simplify, but I have not yet succeeded.

POSTED BY: Mariusz Iwaniuk
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard