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.

  • 1
    $\begingroup$ 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.... $\endgroup$
    – Jean Marie
    Aug 10, 2020 at 16:17
  • $\begingroup$ @JeanMarie I added it now. I basically need it so I could apply the Argument Principle to. $\endgroup$
    – DUO Labs
    Aug 10, 2020 at 16:28

1 Answer 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

  • $\begingroup$ 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! $\endgroup$
    – DUO Labs
    Aug 10, 2020 at 17:52
  • $\begingroup$ 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. $\endgroup$
    – DUO Labs
    Sep 18, 2020 at 20:59
  • $\begingroup$ I appreciate your acceptance and am glad if it was of help to you. $\endgroup$
    – G Cab
    Sep 18, 2020 at 22:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .