title: Printing Big Numbers in Decimal Form
body: <p>Though the representations of a number are somewhat a relative aspect, we
  generally use the decimal form when printing to the outer world.</p>
  
  <p>I'm in a Mac OS X, and while analyzing the source of libc I found that the
  famous <code>printf</code> function ends up calling a little function <code>__ultoa</code> — after
  going through <code>vfprintf_l</code>, the 1104 lines <code>__vfprintf</code> and finally <code>__ultoa</code>.
  It's defined as follows (in this case all these come straight from FreeBSD):</p>
  
  <pre><code>/*
   * Convert an unsigned long to ASCII for printf purposes, returning
   * a pointer to the first character of the string representation.
   * Octal numbers can be forced to have a leading zero; hex numbers
   * use the given digits.
   */
  static CHAR *
  __ultoa(u_long val, CHAR *endp, int base, int octzero, const char *xdigs)
  {
      CHAR *cp = endp;
      long sval;
  
      /*
       * Handle the three cases separately, in the hope of getting
       * better/faster code.
       */
      switch (base) {
      case 10:
          if (val &lt; 10) {     /* many numbers are 1 digit */
              *--cp = to_char(val);
              return (cp);
          }
          /*
           * On many machines, unsigned arithmetic is harder than
           * signed arithmetic, so we do at most one unsigned mod and
           * divide; this is sufficient to reduce the range of
           * the incoming value to where signed arithmetic works.
           */
          if (val &gt; LONG_MAX) {
              *--cp = to_char(val % 10);
              sval = val / 10;
          } else
              sval = val;
          do {
              *--cp = to_char(sval % 10);
              sval /= 10;
          } while (sval != 0);
          break;
  
      case 8:
          do {
              *--cp = to_char(val &amp; 7);
              val &gt;&gt;= 3;
          } while (val);
          if (octzero &amp;&amp; *cp != '0')
              *--cp = '0';
          break;
  
      case 16:
          do {
              *--cp = xdigs[val &amp; 15];
              val &gt;&gt;= 4;
          } while (val);
          break;
  
      default:                /* oops */
          LIBC_ABORT("__ultoa: invalid base=%d", base);
      }
      return (cp);
  }
  </code></pre>
  
  <p>Here <code>CHAR</code> is just typedef'ed to <code>char</code> (for some reason) and <code>to_char</code> does
  basically what you'd expect:</p>
  
  <pre><code>#define to_char(n)  ((n) + '0')
  </code></pre>
  
  <p>The translation to the decimal form occurs in a straightforward way, dividing by
  10 and taking %10:</p>
  
  <pre><code>do {
      *--cp = to_char(sval % 10);
      sval /= 10;
  } while (sval != 0);
  </code></pre>
  
  <p>However, while this work for little numbers (up to 8 bytes) it seems too much
  "manual labor" for me. In GMP, you can easily calculate 2<sup>5000</sup>:</p>
  
  <pre><code>mpz_t n;
  mpz_init(n);
  mpz_ui_pow_ui(n, 2ul, 5000ul);
  gmp_printf("%Zd\n", n);
  </code></pre>
  
  <p>While this has an easy representation for bases 2 or 16, the decimal form is a
  bit harder to calculate.</p>
  
  <p>So, how exactly libraries like GMP handles these? Looks like taking modulo and
  divisions can be expensive for such big numbers. Is there any faster algorithm,
  or am I wrong and the standard process is easy for computers?</p>