Timeline for Approximation of a quadratic map by using a limited binary representation
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 25, 2020 at 11:05 | comment | added | Penelope Benenati | In the problem above, where you provided your answer, it is easy to see that the binary tree $T$ was the full complete binary tree. | |
| Dec 25, 2020 at 11:04 | comment | added | Penelope Benenati | Thank you once again for your help @D.Dona ! The underlying problem is more general and interesting. Given a $h$ bits binary representation of $\log_2(x)$ and $\log_2(y)$, we want to compute $\log_2(z)$ where $z=x\,y+1$. This computation must be repeated several times, namely bottom-up in a binary tree $T$ where $x$ and $y$ are the integers associated with any two siblings children of $z$, starting from the leaves; the value of each leaf is $1$. The goal is to approximate $\log_2(r)$ where $r$ is the value of the root, when $h$ is the ceiling of the logarithm of the number of leaves of $T$. | |
| Dec 25, 2020 at 9:29 | comment | added | D. Dona | Theoretically speaking, I'd say the best bet is to find $c$ exactly, and the asymptotics would give what you want. Even finding an approximation $c_{n}$ accurate to the $n$-th digit is enough to get $a_{n}$ up to multiplicative constant, since $2^{n}|c-c_{n}|$ is bounded: in that case, playing delicately with expansions of $\log(x+1)-\log(x)$ may be sufficient, as I was doing at the beginning of the lower bound sketch. That said, I don't know the practical problems of implementing that on a real computer (if that, as I assume, is your goal). | |
| Dec 24, 2020 at 22:42 | comment | added | Penelope Benenati | Thank you D.Dona . I am now wondering whether we can approximate $a_n$ up to constant multiplicative factor for all $n\le m(h)$, using at most $h$ bits. I guess we could use a third function $c_n(h):=b_n(h)-\gamma(h)\,2^{n-h}$. However, I have no idea about how to find $\gamma(h)$. | |
| Dec 24, 2020 at 22:34 | vote | accept | Penelope Benenati | ||
| Dec 24, 2020 at 22:04 | comment | added | D. Dona | @PenelopeBenenati I added a sketch for the lower bound. | |
| Dec 24, 2020 at 22:03 | history | edited | D. Dona | CC BY-SA 4.0 |
(added lower bound)
|
| Dec 24, 2020 at 21:06 | comment | added | Penelope Benenati | Sorry, I meant that $a_n\sim 2^{c\cdot 2^n}$ for $n\to\infty$, and the asymptotic convergence of $c$ seems to be fast. | |
| Dec 24, 2020 at 20:44 | comment | added | Penelope Benenati | Thank you for your answer. When you write "Say that $n$ is the largest integer with $a_{n}<2^{h}$" I am bit confused because you are denoting by $n$ a quantity, while $n$ was used as a subscript for both $a_n$ and $b_n$. By the way, I am also very interested in bounding $\rho(h)$ from below. Considering that $a_n=2^{c\cdot 2^n}$ for a constant $c\approx 0.587$, may I ask you your opinion also about a lower bound of $\rho(h)$? PS: My final goal is actually to find a method to approximate $a_n$ up to a constant factor using at most $h$ bits. | |
| Dec 24, 2020 at 19:59 | history | answered | D. Dona | CC BY-SA 4.0 |