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...