shiva
/
TipsAndTriks


			
							12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145
							<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- saved from url=(0052)http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html -->
<html lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <title>Jones on Binary to Decimal Conversion</title>
  
  
  <meta name="Author" content="Douglas W. Jones">
  <meta name="Language" content="English">
  <meta name="editor" content="/usr/bin/vi">
  
   <meta name="Description" content="A tutorial on binary to decimal conversion using limited precision">
  
  
  <style type="text/css">
   BODY { margin-left: 3%; margin-right: 3%; }
   H2.SQUAT { margin-top: 0.4em; margin-bottom: 0.25em; }
   H3.SQUAT { margin-top: 0.3em; margin-bottom: 0.2em; }
   H4.SQUAT { margin-top: 0.2em; margin-bottom: 0.15em; }
   H5.SQUAT { margin-top: 0.17em; margin-bottom: 0.15em; }
   * { line-height: 1.1 }
   P.SQUAT { margin-top: 0.25em; margin-bottom: 0.15em; }
   UL.SQUAT { margin-top: 0.25em; margin-bottom: 0.15em; }
   EM.O { font-style: normal; text-decoration: overline; }
   EM.U { font-style: normal; text-decoration: underline; }
   EM.S { font-style: normal; text-decoration: line-through; }
   A { text-decoration: none; }
   A.I { font-style: italic; text-decoration: none; }
   SUP { vertical-align: 0; position: relative; bottom: 1ex; }
   SUB { vertical-align: 0; position: relative; top: 0.8ex; }
   TABLE.BOXY { border: 0; padding: 0; border-spacing: 0;
                border-collapse: collapse; }
   TD.BOX { border: solid; border-width: thin; border-color: DimGray;
	      text-align: center; }
   TD.BOXTT { border: solid; border-width: thin; border-color: DimGray;
	      font-family: monospace; text-align: center; }
   TD.TT { font-family: monospace; text-align: left; }
   TD.TTSPACE { font-family: monospace; text-align: left; color: white }
   TD.SHADE { background: Silver; text-align: center; }
   CAPTION { padding-top: 6px; }
   DIV.HEADBOX { border: groove; border-width: 2px; background: #F0F0E0; padding-top: 1%; padding-bottom: 1%; padding-left: 5px; }
   DIV.HEADBOX P { margin-top: 0.8em; margin-bottom: 0.8em; }
   DIV.HEADBOX H1 { margin-top: 0.2em; margin-bottom: 0.4em; }
   DIV.HEADBOX H2 { margin-top: 0.2em; margin-bottom: 0.4em; }
   DIV.INDENT { border: none; padding-left: 1em }
   DIV.INVISIBLE { font-size: 3px; letter-spacing: -5px; color: white; background: white; }
   DIV.INVISIBLE A:link { color: white; }
   DIV.INVISIBLE A:visited { color: white; }
   DIV.INVISIBLE A:active { color: white; }
   DIV.invisible A:active { color: white; background: white; }
  </style>
 <meta name="viewport" content="width=device-width, initial-scale=1"></head>
 <body bgcolor="#FFFFFF" text="#000000" link="#0000CC" vlink="#880088" alink="#880088">
  <div class="HEADBOX" data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="197.5">
   
   <table border="0" cellspacing="0" cellpadding="0" data-pf_style_display="table" data-pf_style_visibility="visible" data-pf_rect_width="1716" data-pf_rect_height="159"><tbody data-pf_style_display="table-row-group" data-pf_style_visibility="visible" data-pf_rect_width="1716" data-pf_rect_height="159"><tr data-pf_style_display="table-row" data-pf_style_visibility="visible" data-pf_rect_width="1716" data-pf_rect_height="159"><td data-pf_style_display="table-cell" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="159">&nbsp;&nbsp;</td><td data-pf_style_display="table-cell" data-pf_style_visibility="visible" data-pf_rect_width="1708" data-pf_rect_height="158.78125">
    
     <h1 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1708" data-pf_rect_height="35">Binary to Decimal Conversion in Limited Precision</h1>
    
    
    <p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1708" data-pf_rect_height="51">
    
     Part of <a href="http://www.cs.uiowa.edu/~jones/bcd/" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="217.328125" data-pf_rect_height="17">
      
      the Arithmetic Tutorial Collection
      
     </a>
     <br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
     
    
     by
     <a href="http://www.cs.uiowa.edu/~jones/" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="114.234375" data-pf_rect_height="17">Douglas W. Jones</a>
     
     <br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
    
    
    <a href="http://www.uiowa.edu/" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="174.21875" data-pf_rect_height="17">
     T<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="17.78125" data-pf_rect_height="15">HE</small> U<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="70.359375" data-pf_rect_height="15">NIVERSITY</small>
    <small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="17.046875" data-pf_rect_height="15">OF</small> I<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="30.359375" data-pf_rect_height="15">OWA</small></a>
    <a href="http://www.cs.uiowa.edu/" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="214.59375" data-pf_rect_height="17">Department&nbsp;of&nbsp;Computer&nbsp;Science</a>
    
    
     </p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1708" data-pf_rect_height="28">
     <small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="1674.484375" data-pf_rect_height="29">
      Copyright ©
      1999, Douglas. W. Jones, with major revisions made in 2002 and 2010.
      This work may be transmitted or stored in electronic form on any
      computer attached to the Internet or World Wide Web so long as this
      notice is included in the copy.  Individuals may make single copies
      for their own use.  All other rights are reserved.
     </small>
    
   </p></td></tr></tbody></table>
    
  </div>
 

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26">Index</h2>

<ul data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="136">
<li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#intro" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="79.09375" data-pf_rect_height="17">Introduction</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#basic" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="95.953125" data-pf_rect_height="17">The Basic Idea</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#reduce" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="119.984375" data-pf_rect_height="17">Reduction to Code</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#signed" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="194.203125" data-pf_rect_height="17">Dealing with Signed Numbers</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#precision" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="131.96875" data-pf_rect_height="17">Living Within 8 Bits</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#division" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="297.234375" data-pf_rect_height="17">Doing Without Hardware Multiply and Divide</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#radices" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="126.625" data-pf_rect_height="17">Alternative Radices</a>
</li><li data-pf_style_display="list-item" data-pf_style_visibility="visible" data-pf_rect_width="1685.84375" data-pf_rect_height="17"> <a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#sixtyfour" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="249.296875" data-pf_rect_height="17">64-bit Conversion on a 32-bit Machine</a>
</li></ul>

<table border="1" width="100%" data-pf_style_display="table" data-pf_style_visibility="visible" data-pf_rect_width="1725" data-pf_rect_height="24">
 <tbody data-pf_style_display="table-row-group" data-pf_style_visibility="visible" data-pf_rect_width="1723" data-pf_rect_height="22"><tr data-pf_style_display="table-row" data-pf_style_visibility="visible" data-pf_rect_width="1723" data-pf_rect_height="18">
  <td align="CENTER" data-pf_style_display="table-cell" data-pf_style_visibility="visible" data-pf_rect_width="1719" data-pf_rect_height="18">
   <small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="337.453125" data-pf_rect_height="15">
    Rated as a top 50 site by
    <a href="http://www.programmersheaven.com/" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="118.265625" data-pf_rect_height="15">Programmer's Heaven</a>
    as of Feb 2002.
   </small>
  </td>
 </tr>
</tbody></table>

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="intro" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="130.265625" data-pf_rect_height="26"> Introduction </a> </h2>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Programmers on binary computers have always faced computational problems
when dealing with textual input-output because of our convention that printed
numeric data should be represented in base 10.  These problems have never
been insurmountable, but they are particularly annoying when writing programs
for machines with limited capacity in their arithmetic units.  Suppose, for
example, you have an unsigned binary number that you wish to print out in
decimal form.  The following C code will do this:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="84">    void putdec( unsigned int n ) {
        unsigned int rem  = n % 10;
        unsigned int quot = n / 10;
        if (quot &gt; 0) putdec( quot );
        putchar( rem + '0' );
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
The problem with this C code is that it assumes that the computer's arithmetic
unit is sufficiently large to handle the entire number n, and it assumes that
the arithmetic unit can conveniently do integer division yielding both a
quotient and a remainder.  These assumptions are not always reasonable, both
because many commercially successful computers do not include division
hardware and because, even when such hardware is available, it is of little
direct use when dividing numbers larger than the ALU can handle.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="51">
The focus of this tutorial is on writing fast code to convert unsigned 16 bit
binary numbers to decimal on a machine with an 8-bit ALU and no divide
instruction.  This situation is common on small microcontrollers, and the
techniques generalize in useful ways, for example, to the problem of doing
64 bit binary to decimal conversion using a 32 bit ALU.  A final section
of this tutorial examines how these methods can be extended to larger
numbers, for example, converting a 64-bit binary number to decimal on
a machine with a 32-bit ALU.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
On machines with no divide instruction where speed is no issue, it may
be better to simply use repeated subtraction instead of the fast but
algebraically complex code given in the body of this tutorial.
Consider the following 16-bit conversion code as an example.
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="224">    void putdec( int n ) {
        char a, b, c, d;
        if (n &lt; 0) {
            putchar( '-' );
            n = -n;
        }
        for ( a = '0' - 1; n &gt;= 0; n -= 10000 ) ++a;
        for ( b = '9' + 1; n &lt;  0; n += 1000  ) --b;
        for ( c = '0' - 1; n &gt;= 0; n -= 100   ) ++c;
        for ( d = '9' + 1; n &lt;  0; n += 10    ) --d;
        putchar( a );
        putchar( b );
        putchar( c );
        putchar( d );
        putchar( n + '0' );
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Variants on the clever algorithm given above have been very popular on
8-bit microprocessors and microcontrollers, despite the fact that conversions
can require over 30 iterations of the for loops in this code.  As given here,
this code does not work for the extreme negative value -32768; fixing this
bug without introducing a special case is an interesting exercise.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="basic" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="152.015625" data-pf_rect_height="26"> The Basic Idea </a> </h2>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
To do the conversion faster, what we'll do is look at our binary number
as a base 16 number and then do the conversion in terms of the base 16
digits.
Consider a 16 bit number <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i>.  This can be broken into 4 fields of
4 bits each, the base 16 digits; call them <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>,
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> and <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>.
</p><pre width="70" data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="70">                    n
    |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
    |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
    |   n   |   n   |   n   |   n   |
         3       2       1       0
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
The value of the number can be expressed in terms of these 4 fields as
follows:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> = 4096 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 256 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
           16 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>   + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
In the same way, if the value of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i>, expressed in decimal, is
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>, where each of
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>,
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> and <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> are decimal digits, the
value of n can be expressed as:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> = 10000 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> + 1000 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
           100 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>   + 10 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> +
           1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Our problem then, is to compute the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> from the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> without dealing directly with the larger
number <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i>.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
To do this, we first note that the factors used in combining the values of
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> can themselves be expressed as sums of multiples of
powers of 10.  Therefore, we can rewrite the original expression as:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> =
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>( 4×1000 + 0×100 + 9×10 + 6×1 ) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>( 2×100 + 5×10 + 6×1 ) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>( 1×10 + 6×1 ) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>( 1×1 )
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
If distribute the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> over the expressions for each factor,
then factor out the multiples of 100, we get the following:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> =
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 1000 (4<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 100 (0<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 2<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 10 (9<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 5<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
               1<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 1 (6<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 6<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
              6<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> +
      1<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>)
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
We can use this to arrive at first approximations <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>
for <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> through <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> = 4 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> = 0 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 2 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> = 9 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 5 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
                           1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> = 6 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 6 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
                           6 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
The values of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> are not proper decimal digits because
they are not properly bounded in the range
0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> ≤ 9.
Instead, given that each
of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> is bounded in the range
0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> ≤ 15,
the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>
are bounded as follows:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ≤ 60
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> ≤ 30
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> ≤ 225
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> ≤ 285
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
This is actually quite promising because <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> through
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> are less than 256 and may therefore be computed using
an 8 bit ALU, and even <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> may be computed in 8 bits if we
can use the carry-out bit of the ALU to hold the high bit.  Furthermore,
if our interest is 2's complement arithmetic where the high bit is the
sign bit, the first step in the output process is to print a minus sign
and then negate, so the constraint on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> becomes
0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ≤ 8
and we can conclude naively that
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> ≤ 243
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Note that we said
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ≤ 8
and not
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> &lt; 8;
this is because of the one negative number in the 2's complement system
that cannot be properly negated, -32768.  If we exclude this number from
the range of legal values, the upper bound
is reduced to 237; in fact, this is the overall upper bound, because
in the one case where
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> is 8, all of the other
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> are zero, so we can assert globally that
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> ≤ 237
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Even with our naive bound, however, it is easy to see that we can
safely use 8 bit arithmetic to accumulate all of the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Given that we have computed the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>, we can push them
into the correct ranges by a series of 8-bit divisions and one 9-bit division,
as follows:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="221">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="221">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> = <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> / 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> = <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> mod 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>) / 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>) mod 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>) / 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>) mod 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>) / 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>) mod 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> = <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
In the above, the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> terms represent carries propagated
from one digit position to the next.  The upper bounds on each of the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> can be computed from the bounds given above for the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> ≤ 28 [ = 285 / 10 ]
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> ≤ 25 [ = (28 + 225) / 10
                                                    = 253 / 10 ]
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ≤ 5 [ = (25 + 30) / 10 = 55 / 10 ]
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> ≤ 6 [ = (5 + 60) / 10 = 65 / 10 ]
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In computing the bound on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>, we came within 2 of
to 255, the maximum that can be represented in 8 bits, so an 8 bit
ALU is just barely sufficient for this computation.  Again, if we
negate any negative numbers prior to output, so that the maximum
value of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> is 8, the bound on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
becomes 23 instead of 28.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="reduce" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="190.671875" data-pf_rect_height="26">Reduction to Code</a> </h2>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
A first hack at reducing the above idea to code might include named temporaries
for all of the terms used above, but we can avoid this if we reorganize
things slightly and note that, after computing each digit of the number, we
no-longer need one of the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>.  This leads to the
following C code:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="462">    void putdec( uint16_t n ) {
        uint8_t d4, d3, d2, d1, q;
        uint16_t d0;

        d0 = n       &amp; 0xF;
        d1 = (n&gt;&gt;4)  &amp; 0xF;
        d2 = (n&gt;&gt;8)  &amp; 0xF;
        d3 = (n&gt;&gt;12) &amp; 0xF;

        d0 = 6*(d3 + d2 + d1) + d0;
        q = d0 / 10;
        d0 = d0 % 10;

        d1 = q + 9*d3 + 5*d2 + d1;
        q = d1 / 10;
        d1 = d1 % 10;

        d2 = q + 2*d2;
        q = d2 / 10;
        d2 = d2 % 10;

        d3 = q + 4*d3;
        q = d3 / 10;
        d3 = d3 % 10;

        d4 = q;

        putchar( d4 + '0' );
        putchar( d3 + '0' );
        putchar( d2 + '0' );
        putchar( d1 + '0' );
        putchar( d0 + '0' );
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In the above,
we use the standard C types <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="50.046875" data-pf_rect_height="15">uint8_t</tt> and <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="57.1875" data-pf_rect_height="15">uint16_t</tt>
to represent unsigned 8 and 16-bit values.  By convention, these should
be defined in <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="71.484375" data-pf_rect_height="15">&lt;stdint.h&gt;</tt>.
Of course, this code prints all 5 digits of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> instead of only
printing the significant digits, but this can be fixed in many ways.  The
following fix is perhaps the cleanest, making effective use of partial
results as soon as those results can be used to predict that digits will
be zero.  Even so, adding these features to the code obscures the
computation being performed.
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="574">    void putdec( uint16_t n ) {
        uint8_t d4, d3, d2, d1, q;
        uint16_t d0;

        d0 = n       &amp; 0xF;
        d1 = (n&gt;&gt;4)  &amp; 0xF;
        d2 = (n&gt;&gt;8)  &amp; 0xF;
        d3 = (n&gt;&gt;12);

        d0 = 6*(d3 + d2 + d1) + d0;
        q = d0 / 10;
        d0 = d0 % 10;

        d1 = q + 9*d3 + 5*d2 + d1;
        if (d1 != 0) {
            q = d1 / 10;
            d1 = d1 % 10;

            d2 = q + 2*d2;
            if ((d2 != 0) || (d3 != 0)) {
                q = d2 / 10;
                d2 = d2 % 10;

                d3 = q + 4*d3;
                if (d3 != 0) {
                    q = d3 / 10;
                    d3 = d3 % 10;
            
                    d4 = q;
            
                    if (d4 != 0) {
                        putchar( d4 + '0' );
                    }
                    putchar( d3 + '0' );
                }
                putchar( d2 + '0' );
            }
            putchar( d1 + '0' );
        }
        putchar( d0 + '0' );
    }
</pre>

<hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="signed" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="26"></a>Dealing with Signed Numbers</h2>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
To print signed values, we can replace the first few lines of the above
code with the following:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="196">    void putdec( int16_t n ) {
        uint8_t d4, d3, d2, d1, d0, q;

        if (n &lt; 0) {
            putchar( '-' );
            n = -n;
        }

        d0 = n       &amp; 0xF;
        d1 = (n&gt;&gt;4)  &amp; 0xF;
        d2 = (n&gt;&gt;8)  &amp; 0xF;
        d3 = (n&gt;&gt;12) &amp; 0xF;

        /* the remainder of the code is unchanged */
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In the above, we use the standard C type <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="50.046875" data-pf_rect_height="15">int16_t</tt>
to represent signed 16-bit values and <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="50.046875" data-pf_rect_height="15">uint8_t</tt>
to represent unsigned 8-bit values.  By convention, these should
be defined in <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="71.484375" data-pf_rect_height="15">&lt;stdint.h&gt;</tt>.
As mentioned earlier, forcing <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> positive prior to breaking it down
into nibbles allows us to use an 8-bit type for <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="14.296875" data-pf_rect_height="15">d0</tt> instead
of the 16-bit type used previously (only 9 bits were actually needed).
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Note that the computation of <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="14.296875" data-pf_rect_height="15">d3</tt> has also changed as a result of
the change from unsigned to signed arithmetic.  This is because the
right-shift operator shifts zeros into the high bit when applied to
unsigned numbers, but it replicates the sign bit when applied to signed
numbers.  There is one case in 16 bit 2's complement arithmetic where
both <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> and -<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> are negative, that is, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> = -32768.
The change we have made gives us the correct output in this case.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="precision" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="207.859375" data-pf_rect_height="26">Living Within 8 Bits</a> </h2>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In the code given above for unsigned printing, the fact that
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> could be as large as 285 forced us to declare the
variable <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="14.296875" data-pf_rect_height="15">d0</tt> as a 16-bit integer instead of just 8 bits.
We can avoid this by observing that the final addition in the sum
used to compute <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> is the only one that will push
this sum over 255, and therefore, we need only check the carry bit once
to detect overflow.  Having detected overflow, we can account for it in
the computation that follows:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="308">    void putdec( uint16_t n ) {
        uint8_t d4, d3, d2, d1, d0, q;

        d0 = n       &amp; 0xF;
        d1 = (n&gt;&gt;4)  &amp; 0xF;
        d2 = (n&gt;&gt;8)  &amp; 0xF;
        d3 = (n&gt;&gt;12) &amp; 0xF;

        if ( (6*(d3 + d2 + d1) + d0) &gt; 255 ) { /* overflow */
            d0 = (6*(d3 + d2 + d1) + d0) &amp; 0xFF;
            q = d0/10 + 25;
            d0 = d0 % 10 + 6;
            if (d0 &gt;= 10) {
                d0 = d0 - 10;
                q = q + 1;
            }
        } else { /* no overflow */
            d0 = 6*(d3 + d2 + d1) + d0;
            q = d0 / 10;
            d0 = d0 % 10;
        }

</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In the above code, after having noted an overflow in the computation of
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>, we retain the least significant bits of the sum
in <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="14.296875" data-pf_rect_height="15">d0</tt> and then approximately correct the quotient by
adding 256/10, or 25; correcting this and computing the correct
remainder is a bit more interesting.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Given some integer <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> ≥ 256, if we want to compute
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> mod 10 from (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> - 256) mod 10, we need to note that
the modulus operator is distributive in an interesting sense:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
(<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">j</i>) mod <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="11.5625" data-pf_rect_height="17">m</i> =
((<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> mod <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="11.5625" data-pf_rect_height="17">m</i>) + (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">j</i> mod <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="11.5625" data-pf_rect_height="17">m</i>)) mod <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="11.5625" data-pf_rect_height="17">m</i>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Using this, we can conclude that:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="34">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="34">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> mod 10 = (((<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> - 256) mod 10) + (256 mod 10)) mod 10
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"> = (((<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> - 256) mod 10) + 6) mod 10
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In the case where ((<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i> - 256) mod 10) + 6 is greater than 10,
the truncation of the quotient was also incorrect, so we must add 1
to the approximate quotient as well.  This justifies the code given above,
and this code has also been tested exhaustively for all integers from
0 to 65535.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="division" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="475.40625" data-pf_rect_height="26">Doing Without Hardware Multiply and Divide</a> </h2>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
If flat-out speed is not of the essence, the easiest way to do the
required divisions is to use the trivial repeated subtraction algorithm.
The largest dividend we must consider is only 285, so it will take no
more than 28 iterations for this division.
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="154">    /* quotient and remainder returned by div10 */
    unsigned char q, r;

    void div10( uint8_t i ) {
        q = 0;
        r = i;
        while (r &gt; 9) {
                q = q + 1;
                r = r - 10;
        }
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
This can be optimized in several ways.  Most notably, termination conditions
that compare with zero are almost always significantly faster than those
that compare with other constants, so we might be tempted to write something
like this:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="168">    /* quotient and remainder returned by div10 */
    uint8_t q, r;

    void div10( uint8_t i ) {
        q = -1;
        r = i;
        do {
                q = q + 1;
                r = r - 10;
        } while (r &gt;= 0); /* see note below */
        r = r + 10;
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
The above C code is wrong because <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.15625" data-pf_rect_height="15">r</tt> is declared to be unsigned leading
to the fact that the comparison <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="28.59375" data-pf_rect_height="15">r&gt;=0</tt> will always return true.
Note that in assembly language, this code can be fixed by terminating the loop
when the condition codes indicate a borrow after the <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="28.59375" data-pf_rect_height="15">r-10</tt> subtraction.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
<a href="http://homepage.cs.uiowa.edu/~jones/bcd/divide.html" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="196.40625" data-pf_rect_height="17">Another section of this tutorial</a>
covers the problem of doing multiplicaton and division using only shift
and add instructions.  We use the results presented there, taking specific
advantage of the limited ranges of values occupied by our dividends, to
completely eliminate iteration from our code.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
There are two ways to get an exact quotient and remainder from
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="4.453125" data-pf_rect_height="17">i</i>/10 using reciprocal multiplication in 8 bits.
Either we multiply by 0.00011001 to get an approximate quotient and then
compute the remainder and correct the quotient, or we multiply by
0.00011001101 to get an exact quotient from which we can compute the
remainder.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
The former method, yielding an approximation, can be reduced to the
following C code:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="252">    /* quotient and remainder returned by div10 */
    uint8_t q, r;

    void div10( uint8_t i ) {
        /* approximate the quotient as q = i*0.000110011 (binary) */
        q = ((i&gt;&gt;1) + i) &gt;&gt; 1; /* times 0.11 */
        q = ((q&gt;&gt;4) + q) &gt;&gt; 3; /* times 0.000110011 */

        /* compute the reimainder as r = i - 10*q */
        r = ((q&lt;&lt;2) + q) &lt;&lt; 1; /* times 1010. */
        r = i - r;

        /* fixup if approximate remainder out of bounds */
        if (r &gt;= 10) {
            r = r - 10;
            q = q + 1;
        }
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In first two right-shift-and-add statements used above, we have
assumed that the carry out of the high bit of the add operation
is shifted into the high bit of the second of the two right-shift
operations used in each statement.  This can be done efficiently
in many machine instruction sets, but even good optimizing compilers
may insist on using a 16 bit accumulator for all intermediate
results of arithmetic operations.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
The second approach, using a more elaborate multiplier to give an
exact quotient, may be coded as follows:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="196">    /* quotient and remainder returned by div10 */
    uint8_t q, r;

    void div10( uint8_t i ) {
        /* approximate the quotient as q = i*0.00011001101 (binary) */
        q = ((i&gt;&gt;2) + i) &gt;&gt; 1; /* times 0.101 */
        q = ((q   ) + i) &gt;&gt; 1; /* times 0.1101 */
        q = ((q&gt;&gt;2) + i) &gt;&gt; 1; /* times 0.1001101 */
        q = ((q   ) + i) &gt;&gt; 4; /* times 0.00011001101 */

        /* compute the reimainder as r = i - 10*q */
        r = ((q&lt;&lt;2) + q) &lt;&lt; 1; /* times 1010. */
        r = i - r;
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
The particular choice of one or the other of these schemes can only be
made after compiling them or hand translation to machine code.  Depending
on the specific features offered by the target architecture, either of the
above may be the fastest or most compact, and careful use of small
optimizations may tilt the balance one way or the other.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Depending on the space-time tradeoffs of the application, the above
code may be expanded in-line as an open macro, or it may be called as a
closed function.  If in-line expansion is appropriate, it should be noted
that the computations of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> and <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub>
involve dividends no greater than 65.  For dividends up to 68, the
multiplier 0.0001101 gives exact results, suggesting the following version
of the print routine:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="476">    void putdec( int16_t n ) {
        uint8_t d4, d3, d2, d1, d0, q;

        if (n &lt; 0) {
            putchar( '-' );
            n = -n;
        }

        d1 = (n&gt;&gt;4)  &amp; 0xF;
        d2 = (n&gt;&gt;8)  &amp; 0xF;
        d3 = (n&gt;&gt;12) &amp; 0xF;

        d0 = 6*(d3 + d2 + d1) + (n &amp; 0xF);
        q = (d0 * 0xCD) &gt;&gt; 11;
        d0 = d0 - 10*q;

        d1 = q + 9*d3 + 5*d2 + d1;
        q = (d1 * 0xCD) &gt;&gt; 11;
        d1 = d1 - 10*q;

        d2 = q + 2*d2;
        q = (d2 * 0x1A) &gt;&gt; 8;
        d2 = d2 - 10*q;

        d3 = q + 4*d3;
        d4 = (d3 * 0x1A) &gt;&gt; 8;
        d3 = d3 - 10*d4;

        putchar( d4 + '0' );
        putchar( d3 + '0' );
        putchar( d2 + '0' );
        putchar( d1 + '0' );
        putchar( d0 + '0' );
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
All multiplications in the above code can be reduced to short sequences
of shift and add instructions, and it is straightforward to add the code
discussed earlier to suppress leading zeros from this code.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
All of these details are incorporated into the attached
<a href="http://homepage.cs.uiowa.edu/~jones/bcd/decimalpic.html" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="428.34375" data-pf_rect_height="17">
decimal print routine for the 14-bit family of PIC microcontrollers.</a>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="radices" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="201.953125" data-pf_rect_height="26">Alternative Radices</a> </h2>

<blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14"><small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="378.484375" data-pf_rect_height="15">
<b data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="31.09375" data-pf_rect_height="15">Note:</b>  The following section was added between
August 6 and 8, 2012.  
</small>
</p></blockquote>

<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
All of the above work was based on dividing the 16-bit number to be printed
into four 4-bit chunks.  That is, we worked in radix 16.  In fact, there is
no reason to work in a fixed radix.  Consider, for example, breaking a
16-bit number into 4 chunks as follows:
</p><pre width="70" data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="70">                    n
    |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
    |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
    |  n  |   n   |   n   |    n    |
        3      2       1        0
</pre>
<blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> = 8192 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 512 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
           32 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>   + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
This leads to the following initial approximations for the decimal digits
of the number:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> = 8 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> = 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 5 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> = 9 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
                           3 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> = 2 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 2 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
                           2 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Shifting to a mixed radix system instead of pure base 16 has the net effect
of changing the range of values in each of initial approximations for the
decimal digits:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ≤ 65
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> ≤ 95
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> ≤ 133
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> ≤ 105
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Enlarging <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> to 5 bits had no major effect because the
multiplier on that term is 1.  Shifting the other terms over one place
changed 3 multiplers from 6 to 12, resulting in smaller terms.
As a result, 8-bit arithmetic now suffices for all of the computations.
Reducing this to C code, we get:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="420">    void putdec( uint16_t n ) {
        uint8_t d4, d3, d2, d1, d0, q;

        d0 = n       &amp; 0x1F;
        d1 = (n&gt;&gt;5)  &amp;  0xF;
        d2 = (n&gt;&gt;9)  &amp;  0xF;
        d3 = (n&gt;&gt;13) &amp;  0x7;

        d0 = 2*(d3 + d2 + d1) + d0;
        q = (d0 * (uint16_t)0x67) &gt;&gt; 10;
        d0 = d0 - 10*q;

        d1 = 9*d3 + d2 + 3*d1 + q;
        q = (d1 * (uint16_t)0x67) &gt;&gt; 10;
        d1 = d1 - 10*q;

        d2 = d3 + 5*d2 + q;
        q = (d2 * (uint16_t)0x67) &gt;&gt; 10;
        d2 = d2 - 10*q;

        d3 = 8*d3 + q;
        q = (d3 * (uint16_t)0x1A) &gt;&gt; 8;
        d3 = d3 - 10*q;

        putchar(q  + '0');
        putchar(d3 + '0');
        putchar(d2 + '0');
        putchar(d1 + '0');
        putchar(d0 + '0');
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Enlarging <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> to 5 bits had a second consequence.  Because
the upper bounds on the larger terms have been reduced, shortened
approximations for one tenth can be used.  On small
microcontrollers without hardware support for multiplication, this can
result in savings of a few instructions per multiply.
The multiplier 67<sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="13.34375" data-pf_rect_height="15">16</sub> works because 0.0001100111 approximates one
tenth to sufficient precision to divide any number less than 179 by ten.
The final digit, <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="14.296875" data-pf_rect_height="15">d3</tt>, can still be computed
using the even shorter approximation we used previously.

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<h2 data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="26"> <a name="sixtyfour" data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="394.015625" data-pf_rect_height="26">64-bit Conversion on a 32-bit Machine</a> </h2>

<blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14"><small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="1248.890625" data-pf_rect_height="15">
<b data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="31.09375" data-pf_rect_height="15">Note:</b>  The following section was added on
June 8, 2010.  As of June 10, the constants given in this section
and the code at the end have been checked
and appear to be correct.  As of August 13, this code has
undergone extensive testing.
</small>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="51">
The techniques explored above are applicable wherever a large integer
must be converted to decimal on a machine with a smaller ALU.  For
example, consider the problem of converting 64-bit integers to decimal
on a machine with a 32-bit ALU.  This practical problem comes up, for
example, in the BIOS code for Intel-architecture machines, where the
code must not assume a 64-bit CPU but must still be able to report
64-bit values when it reports on such things as the sizes of the
attached disk drives.  When 64-bit arithmetic is supported on a 32-bit
machine, it is slow enough that significant speedups can be achieved
by avoiding it.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
In general, 64-bit values may have up to 20 decimal digits:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
2<sup data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="13.34375" data-pf_rect_height="15">64</sup> = 18,446,744,073,709,551,616
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Normally, we group decimal digits in groups of 3 using commas, as
illustrated above.  This is equivalent to writing the number in base 1000,
where each base 1000 digit is represented with 3 consecutive decimal digits.
Because there are 20 digits, grouping them as 5 blocks of 4 makes sense,
suggesting that we should work in base 10,000.  In addition, 10,000
is the largest power of 10 that can be represented in 16 bits
(half the precision of our ALU).  Therefore, we will write:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
2<sup data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="13.34375" data-pf_rect_height="15">64</sup> = 1844,6744,0737,0955,1616
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
We begin by breaking our 64-bit number into 16-bit chunks, just as we
began the 16-bit conversion by breaking the number into 4-bit chunks.
Again, we will the number <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> and we will call the 16-bit chunks
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
and <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>.
</p><pre width="70" data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="70">                    n
    |___ ___ ___ ___ ___ ___ ___ ___|  64-bits
    |___|___|___|___|___|___|___|___|  8 bytes
    |   n   |   n   |   n   |   n   |  4 16-bit chunks
         3       2       1       0
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
The value of the number can be expressed in terms of these 4 fields as
follows:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="118">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="17">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> = 2<sup data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="13.34375" data-pf_rect_height="15">48</sup><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
           2<sup data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="13.34375" data-pf_rect_height="15">32</sup><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
           2<sup data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="13.34375" data-pf_rect_height="15">16</sup><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> +
           2<sup data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sup><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> =
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  281,474,976,710,656 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  4,294,967,296 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  65,536 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Because we are interested in working in base 10,000, we will regroup the
digits above and continue with the following version:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> =
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  281,4749,7671,0656 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  42,9496,7296 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  6,5536 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Our goal is to express <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> in base 10,000 as
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>.
If each of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>, <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>,
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> and <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> is a single base 10,000
digit, the value of n can be expressed as:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="102">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="102">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> =
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1,0000,0000,0000,0000 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1,0000,0000,0000 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1,0000,0000 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1,0000 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp;  1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Our initial approximations of the decimal digits comes from rearranging
the base 10,000 digits of the multipliers for the 16-bit chunks to conform
with the above decimal presentation:
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="85">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i> =
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 1,0000,0000,0000 ( 281 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 1,0000,0000 ( 4749 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
                         42 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> ) +
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 1,0000 ( 7671 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 9496 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
                    6 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> ) + 
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">&nbsp; 1 ( 0656 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 7296 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
               5536 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> )
</blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
The approximations for the four least significant base 10,000 digits fall out
of the above:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> = 281 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> = 4749 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + 42 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> = 7671 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
                           9496 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> + 6 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> = 0656 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> +
                           7296 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> +
                           5536 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + 1 <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
At this point, just as we did with the 4-bit example, we should check the
range of values we might encounter in each approximation.  Here, our
concern is that some of the approximations might exceed the capacity of a
32-bit ALU.  The maximum value of each term will occur when all of the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> are at their maximum value, which is 65,535.
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>
		≤ 18,415,335
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>
		≤ 313,978,185
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
		≤ 1,125,432,555
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">0 ≤ <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
		≤ 884,001,615
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
All of our approximations are comfortably less than 2 billion, which means
that we can safely use 32-bit signed division, if that is all that is
available to us.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
We are now ready to compute the final values of the digits by a
series of 32-bit divisions, as follows:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="221">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="221">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
	= <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> / 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub>
	= <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> mod 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>
	= (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>) / 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>
	= (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>) mod 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>
	= (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>) / 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>
	= (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>) mod 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub>
	= (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>) / 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>
	= (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>) mod 10,000
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17">
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">d</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> = <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub>
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
In the above, the <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> terms represent carries propagated
from one digit position to the next.  The upper bounds on each of the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub> can be computed from the bounds given above for the
<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="3.71875" data-pf_rect_height="15">i</sub>:
</p><blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="68">
    <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> ≤ 88,400
         [ = <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">0</sub> / 10,000 = 884,001,615 / 10,000 ]
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> ≤ 112,552
         [ = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">1</sub>) / 10,000
           = 1,125,520,955 / 10,000 ]
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> ≤ 31,409
         [ = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">2</sub>) / 10,000
           = 314,090,737 / 10,000 ]
<br data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="0" data-pf_rect_height="17"><i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> ≤ 1,844
         [ = (<i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">a</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub> + <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">3</sub>) / 10,000
           = 18,446,744 / 10,000 ]
</p></blockquote>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="17">
Note something encouraging:  The largest intermediate value encountered
above is 1,125,520,955, which is safely less than 2 billion and therefore
safe to represent as either a signed or unsigned integer on a 32-bit machine.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
Note also that the bound on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="7.109375" data-pf_rect_height="17">c</i><sub data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="6.671875" data-pf_rect_height="15">4</sub> is a small but useful
check on our arithmetic.  The value, 1,844, is identical to the first 4 decimal
digits of 2**64, which is exactly what we expect.  This does not eliminate
the possibility that the above might contain many small clerical errors.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
The code to print the 64-bit number ends up essentially identical to the
code given previouly to print a 16-bit number, except for the sizes of the
variables, the values of the various constants, and the code to print each
digit of the result.
If we have not made any errors in computing the various constants,
the following C code should work:
</p><pre data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="448">    void putdec( uint64_t n ) {
        uint32_t d4, d3, d2, d1, d0, q;

        d0 = n       &amp; 0xFFFF;
        d1 = (n&gt;&gt;16) &amp; 0xFFFF;
        d2 = (n&gt;&gt;32) &amp; 0xFFFF;
        d3 = (n&gt;&gt;48) &amp; 0xFFFF;

        d0 = 656 * d3 + 7296 * d2 + 5536 * d1 + d0;
        q = d0 / 10000;
        d0 = d0 % 10000;

        d1 = q + 7671 * d3 + 9496 * d2 + 6 * d1;
        q = d1 / 10000;
        d1 = d1 % 10000;

        d2 = q + 4749 * d3 + 42 * d2;
        q = d2 / 10000;
        d2 = d2 % 10000;

        d3 = q + 281 * d3;
        q = d3 / 10000;
        d3 = d3 % 10000;

        d4 = q;

        printf( "%4.4u", d4 );
        printf( "%4.4u", d3 );
        printf( "%4.4u", d2 );
        printf( "%4.4u", d1 );
        printf( "%4.4u", d0 );
    }
</pre>
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
In the above code, we used the standard types
<tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="57.1875" data-pf_rect_height="15">uint32_t</tt> and <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="57.1875" data-pf_rect_height="15">uint64_t</tt> to declare
32 and 64-bit unsigned integer variables.  By convention, these should
be defined in <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="71.484375" data-pf_rect_height="15">&lt;stdint.h&gt;</tt>.  Note that
if you are working on a 32-bit machine with no support for 64-bit arithemtic,
there is no guarantee that you will be able to declare the 64-bit type
and you may have to fake it, for example, by representing each 64-bit
value as a pair of 32-bit components.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="34">
This code uses <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="57.1875" data-pf_rect_height="15">printf()</tt> to print each 4-digit base 10,000 digit
of the result.  Of course, this code prints all 20 digits of <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="8" data-pf_rect_height="17">n</i>.
Suppressing leading zeros takes
a bit more work than it did with the 4-bit nibble code because of the
complexity of suppressing leading zeros within the printed representation
of the first nonzero base 10,000 digit.
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="0">

</p><hr data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1725.84375" data-pf_rect_height="2">

<blockquote data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="254">
<p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="1286.265625" data-pf_rect_height="15">
I don't know where I first encountered the basic idea for the 8-bit
code presented here.  This tutorial began as an attempt to reinvent
that code after I found myself working on a machine with an 8-bit ALU
and needing to do 16-bit conversions.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="754.4375" data-pf_rect_height="15">
Thanks to Mark Ramsey, who, on January 22, 2007 pointed out two small typos
with big consequences in the section on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="106.28125" data-pf_rect_height="15">Living Within 8 Bits</i>.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="1136.6875" data-pf_rect_height="15">
Thanks to Dennis Vlasenko, who, on June 15, 2007 pointed out more typos in
the section on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="188.828125" data-pf_rect_height="15">Doing Without Multiply and Divide</i>, and for his work
integrate the 16-bit code into the Linux distribution of <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="59.546875" data-pf_rect_height="13">vsprintf()</tt>.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="484.625" data-pf_rect_height="15">
Thanks to Joe Zbiciak, who, on August 23, 2007 pointed out a small error
the introduction.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="1216.828125" data-pf_rect_height="15">
Thanks to Derick Moore, who, on June 10, 2010, reported that he had
checked the constants and tested the code in the section
on <i data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="204" data-pf_rect_height="15">64-bit conversion on a 32-bit machine</i> and verified that it
worked in the BIOS he was maintaining.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="892.5" data-pf_rect_height="15">
Thanks to Michal Nazarewicz for additional testing reported on August 13, 2010
and for his work to integrate the 64-bit code into the Linux distribution
of <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="59.546875" data-pf_rect_height="13">vsprintf()</tt>.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="987.078125" data-pf_rect_height="15">
Thanks to George Spelvin, who on August 3, 2012, suggested that there is no
reason that all of the chunks should be the same size, leading to the
addition of the section on other radices.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="811.6875" data-pf_rect_height="15">
Thanks to Ralph Corderoy, who on Septeber 10, 2014, pointed out the weakness
of the repeated subtraction code when presented with the value -32768.
</small>
</p><p data-pf_style_display="block" data-pf_style_visibility="visible" data-pf_rect_width="1645.84375" data-pf_rect_height="14">
<small data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="915.734375" data-pf_rect_height="15">
Thanks to Ben Boldt, who on April 9, 2018,
pointed out an error the first take on optimising <tt data-pf_style_display="inline" data-pf_style_visibility="visible" data-pf_rect_width="29.78125" data-pf_rect_height="13">div10</tt> at the start
of the section on doing without hardware multiply and divide.
</small>
</p></blockquote>


</body></html>