Converting from decimal to non-decimal and printing(no strings, arrays and recursion)

Question

Need help with a idea of how to convert a decimal number to non-decimal form(any, given by user input) and print it. The limitations are that arrays and strings are not allowed and while I wrote a recursive function for that, I am thinking of a non-recursive method for the same thing.

More of a personal challenge/exercise than anything vital/serious so feel free to tell me where to shove myself.

Note: I am working in C for this exercise.

Answer 1

Recall that a number x in base B is represented as such: x = a_nBⁿ + ... + a₂B² + a₁B + a₀, where 0≤a_i<B. Note that dividing x by B gives a_nB^n-1 + ... + a₂B + a₁ with remainder a₀ / B. In other words, x mod B = a₀ (mod is short for modulus, which is the remainder after division).

Implemented as an algorithm:

var x    = POSITIVE_INTEGER
var base = POSITIVE_INTEGER2
while x > 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.

This will print the digits in the reverse order.

Workaround: Instead of modulating to get the least significant digit, we modulate to get the most significant digit. We do this by noting that x - (x mod Bⁿ) = a_n, where n is the most significant digit.

var x    = POSITIVE_INTEGER
var base = POSITIVE_INTEGER2
var bn   // This is base**n, where `n` is the most significant digit.
while x > 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.

bn can be calculated as base ** math.floor(math.log(x) / math.log(base)) or by doing

var bn = 1
while bn * base < x
    bn = bn * base