Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Recall that a number <code>x</code> in base <code>B</code> is represented as such: <b><i>x = a<sub>n</sub>B<sup>n</sup> + ... + a<sub>2</sub>B<sup>2</sup> + a<sub>1</sub>B + a<sub>0</sub></i></b>, where <i>0&le;a<sub>i</sub>&lt;B</i>. Note that dividing <code>x</code> by <code>B</code> gives <i>a<sub>n</sub>B<sup>n-1</sup> + ... + a<sub>2</sub>B<sup></sup> + a<sub>1</sub></i> with remainder <i>a<sub>0</sub> / B</i>. In other words, <b><i>x </i>mod<i> B = a<sub>0</sub></i></b> (<i>mod</i> is short for <i>modulus</i>, which is the remainder after division).</p> <p>Implemented as an algorithm:</p> <pre><code>var x = POSITIVE_INTEGER var base = POSITIVE_INTEGER2 while x &gt; 0 print(x mod base) x = x div base // Where "div" is integer division, equivalent to math.floor(x/base) // This way we are discarding a_0. // Next iteration we will get a_1, then a_2, etc. </code></pre> <p>This will print the digits in the reverse order.</p> <p>Workaround: Instead of modulating to get the least significant digit, we modulate to get the most significant digit. We do this by noting that <b><i>x - (x </i>mod<i> B<sup>n</sup>) = a<sub>n</sub></i></b>, where <code>n</code> is the most significant digit.</p> <pre><code>var x = POSITIVE_INTEGER var base = POSITIVE_INTEGER2 var bn // This is base**n, where `n` is the most significant digit. while x &gt; 0 print(x - x mod bn) // Print out a_n x = x mod bn // Discard a_n bn = bn / base // Next iteration get a_(n-1), then a_(n-2), etc. </code></pre> <p><code>bn</code> can be calculated as <code>base ** math.floor(math.log(x) / math.log(base))</code> or by doing</p> <pre><code>var bn = 1 while bn * base &lt; x bn = bn * base </code></pre>
    singulars
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload