1
$\begingroup$

I have a large number $N=O(2^k)$. For simplicity, let's say that $N=n^k$.

However, I only need the $n$-th bits of $N$, say for example the 10-th to 16-th bit of N... without calculating the full expansion...

Is there a simple way to get these? A bit-twiddling hack for instance.

If $b_i\in{b_1,b_2,b_3,b_4}$, with $k=3$, we get the expansion:

$ \left(\sum b_i 2^i\right)^3=8 b_1^3 + 48 b_1^2 b_2 + 96 b_1 b_2^2 + 64 b_2^3 + 96 b_1^2 b_3 + 384 b_1 b_2 b_3 + 384 b_2^2 b_3 + 384 b_1 b_3^2 + 768 b_2 b_3^2 + 512 b_3^3 + 192 b_1^2 b_4 + 768 b_1 b_2 b_4 + 768 b_2^2 b_4 + 1536 b_1 b_3 b_4 + 3072 b_2 b_3 b_4 + 3072 b_3^2 b_4 + 1536 b_1 b_4^2 + 3072 b_2 b_4^2 + 6144 b_3 b_4^2 + 4096 b_4^3 $

This does not however give me an easy wat of obtaining the $n$-th bit of $(2700)_2=1101001 01111000$...

Would a spiggot algorithm work here like for the Bailey-Borwein-Plouffe formula?

Furthermore, this clearly seems to be a number basis conversion problem since we are converting a base $n$ number to a base $2$ number.

Since N is an integer, another way would be to shift the binary expansion of N and take the least significant bit... But this forces me to know the binary expansion... which I do not know beforehand...

$\endgroup$
  • $\begingroup$ The $k$th bit of $N$ is equal to $\ \ \left \lfloor \frac{N}{2^k} \right \rfloor \mod 2$. $\endgroup$ – r.e.s. May 26 '14 at 22:29
  • $\begingroup$ This however forces me to compute $n^k$... Let's assume that $n^k$ is expensive to compute... $\endgroup$ – user13675 May 26 '14 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.