2

Thanks to this answer, I know that to get the $i$th bit of a number $n$, you can do $$\left\lfloor\frac{n}{2^i}\right\rfloor-2\left\lfloor\frac{n}{2^{i+1}}\right\rfloor$$ However, I need this formula to be meromorphic (I'm trying to create a function that I could apply the Argument Principle to). Of course, the floor function isn't meromorphic, so I need an approximation (hopefully with some kind of constant $k$ that I can change to decrease the error). I would also like for it to be efficient (the number of terms are constant or proportional with $\log_2(n)$)

I would make this question just about the floor function, however, if there's some other approximation that uses some other formula to find the $i$th bit, I'm all ears.

DUO Labs
  • 788
  • 1
    Could you say a little more about your motivation for finding a $w=f(z)$ approximation ? It could help. A priori, it's not evident : you have very different mathematical "worlds" (complex function theory and binary representations) that are not accustomed to invite one another at their respective homes.... – Jean Marie Aug 10 '20 at 16:17
  • @JeanMarie I added it now. I basically need it so I could apply the Argument Principle to. – DUO Labs Aug 10 '20 at 16:28

1 Answers1

1

Consideration (too long for a comment)

We might think to shift to the fractional part $\{ \left\{ x \right\}$ $$ x = \left\lfloor x \right\rfloor + \left\{ x \right\}\quad \left| {\,0 \le \left\{ x \right\} < 1} \right. $$ so that $$ \left\lfloor {{n \over {2^k }}} \right\rfloor - 2\left\lfloor {{n \over {2^{k + 1} }}} \right\rfloor = {n \over {2^k }} - \left\{ {{n \over {2^k }}} \right\} - 2{n \over {2^{k + 1} }} + 2\left\{ {{n \over {2^{k + 1} }}} \right\} = 2\left\{ {{n \over {2^{k + 1} }}} \right\} - \left\{ {{n \over {2^k }}} \right\} $$

The $\left\{ x \right\}$ in itself is just a [sawtooth wave] (https://en.wikipedia.org/wiki/Sawtooth_wave), which can be well approximated by its Fourier series.
However the Fourier approximation gets bad while approaching the peaks, which would be amplified by the difference above .

So this kind of approach needs to be examinated more carefully in consideration of the intended use

G Cab
  • 35,272
  • This is good! I'll look into it a bit more. You're right, the peaks really mess it up. But thanks for the start! – DUO Labs Aug 10 '20 at 17:52
  • I just saw this question while searching for something, and realized I didn't accept your answer! Well, in any case, an accept is much overdue. – DUO Labs Sep 18 '20 at 20:59
  • I appreciate your acceptance and am glad if it was of help to you. – G Cab Sep 18 '20 at 22:02