Bounds of eta in blog post

[DanShaders]

I'm trying to recreate lookup tables for the algorithm, and it seems like the first thing to do is to calculate Q for all of the $(e, k)$ pairs. I wrote the following script to do so. The problem is that it returns smaller values for $Q$ than the ones mentioned in your blog post. For example, it returns $Q=110$ for $\eta=1$ and, what is more interesting, $Q = 183$ for $\eta = 23$.

get_bounds function, which is responsible for finding best rational approximations, seems to pass stress testing (see lines 77-90), so I'm fairly certain that it works. However, I'm clueless how to debug this further, since I haven't found code which calculates original values in the repo.

I know that this issue looks like "please, debug my random piece of code", so feel free not to help me and close the issue :)

[jk-jeon]

Thanks a lot for your attention!

You may be right that lesser $Q$ could be still feasible. I guess probably the most relevant difference between what I did and what you did is the fact that I intentionally doubled the range of $n$, for possible application into parsing. (This doubling stuff is explained in the head of the section "The core idea".)

If you follow that route, then $Q=110$ for $\eta=1$ is definitely not enough. For example, consider $e=-459$ and $k=330$ so that $x = 2^{-459 + 330 - 1} \cdot 5^{330}$ (note the $-1$ in the first exponent, which is coming from that I doubled the range). Note that $x$ is still not an integer so there still are remaining digits in $x$. In this case, if you set $Q=110$, then

$$ m = \left\lceil \frac{x \cdot 2^{110}}{10} \right\rceil $$

and what we are hoping to have is

$$ (\lfloor nx \rfloor\ \mathrm{mod}\ 10) = \left\lfloor \frac{10(nm\ \mathrm{mod}\ 2^{Q})}{2^{Q}} \right\rfloor $$

for $n=1,\ \cdots\ ,2^{54}-1$. However, this does not hold for $n=15839737805490946$ (which is between $2^{53}$ and $2^{54}$), as the LHS is $6$ while the RHS is $7$.

Another difference is that I used a slightly different formula to take account of rounding. This stuff is explained in the section on rounding. But that's unlikely a big deal, as it usually just shifts $e$ by $1$ or something like that and nothing more.

Also, even if $\eta=23$ might be also possible with $192$-bit cache blocks, I am currently thinking of replacing $\eta=22$ by $\eta=18$ anyway, because that will result in a faster code but with only a slightly larger table. It also simplifies some other things of the implementation, so maybe it's just a better choice overall.

By the way, the source code for doing this stuff is here, if you want to check it out.

[jk-jeon]

Ah, sorry, please ignore the previous comment. Since the $n$ I brought up is an even number, this still happens even if the range is not doubled: again, set $x = 2^{-459 + 330} \cdot 5^{330}$ (now without $-1$) and

$$ m = \left\lceil \frac{x \cdot 2^{110}}{10} \right\rceil $$

then

$$ (\lfloor nx \rfloor\ \mathrm{mod}\ 10) = \left\lfloor \frac{10(nm\ \mathrm{mod}\ 2^{Q})}{2^{Q}} \right\rfloor $$

fails to hold for $n=7919868902745473$ (the half of the previous $n$), which is in the range $1,\ \cdots\ ,2^{53}-1$. As before, the LHS is $6$ while the RHS is $7$.

I will look into the source code later today.

[DanShaders]

Yeah, looks like the crucial part I've missed is that it is not enough for the interval to have length at least $\frac{D}{2^Q}$. I have just tried to make it also consider the way how we calculate $m$, but it then started to think 192 bits are not enough. But that looks much easier to debug than the original issue. Thanks!
Nonetheless, assuming the code I posted does what I think it should do, it might be possible to store additional bitmap for $(e, k)$ pairs for which $m$ should be less by 1, make $\eta = 25$, and check if this results in faster run time.

[jk-jeon]

You mean, since $m$ will be either the floor or the ceiling of $\frac{2^{Q}x}{D}$, you just encode that as yet another table and look it up? That's a cool idea indeed. I haven't really thought of such a possibility. Even if it doesn't make the code faster, it certainly has some potential to reduce the size of the table.

[DanShaders]

you just encode that as yet another table and look it up?

Yes, exactly.

Regarding my previous message:

but it then started to think 192 bits are not enough.

It turns out that 192 bits are indeed not enough for all of the pairs with the current approach (for instance, for $e=-605$, $k=399$). However, your particular choice of $k_{min}$ makes this and all of the other counterexamples "irrelevant". Not sure if this is (or should be) mentioned somewhere.

And I have yet another question. There is a comment here regarding the second segment. I understand why it cannot be moved and can overlap with the first one (since otherwise we would have defeated the optimization of storing $\eta$ times less powers of 5) but I don't understand why the leading zeroes are relevant there.

[jk-jeon]

It turns out that 192 bits are indeed not enough for all of the pairs with the current approach (for instance, for $e=-605$, $k=399$). However, your particular choice of makes this and all of the other counterexamples "irrelevant". Not sure if this is (or should be) mentioned somewhere.

I'm assuming you're talking about the case $\eta=22$. You're right that my explanation on the blog can be a bit misleading about this. Indeed 192-bit is not enough for all $(e,k)$ pairs satisfying the inequality, and you are right in that exactly because we do not care about all such pairs, 192-bit is actually enough. (And that we pick only one $k$ per each $\eta$-many $k$'s is precisely the point of having $\eta$.) A short explanation about $k_{\min}$ is given at the end of the "Which $(e,k)$-pairs are relevant?" section.

And I have yet another question. There is a comment here regarding the second segment. I understand why it cannot be moved and can overlap with the first one (since otherwise we would have defeated the optimization of storing $\eta$ times less powers of 5) but I don't understand why the leading zeroes are relevant there.

What I mean is that (1) we don't want those leading zeros to be printed, and (2) especially on an invalid buffer region, possibly pointing before the start of the buffer. As a result, we need to find a position in the middle of the second segment where we can start printing digits, which might be right after the end of the first segment (which I believe is what my implementation is doing) or it still might have some overlap with the first segment, but is guaranteed to be safe to write, and we should anyway know how many digits are overlapping.

That's a cool idea indeed. I haven't really thought of such a possibility.

It seems that it requires the table size to be doubled, for most of the choice of $\eta$... so maybe not a good idea.