Decimal Addition! 7/5/93 David Harmon Basic ideas: If we start on a blank, scan right If we start on a '+', jump to "wrapup" Scan past 0/1 to right for '+'. When located, erase it, move to left, record the next digit in state, and replace that with a new +. Then scan right for end of both digit strings. Using state and final '01', record an "A" or "B" representing 0/1 resp. If necessary, carry a one into the 0/1s. Now scan left, past plus. Start from beginning. Wrapup: delete the plus and scan right for A/B, converting A/B to 0/1. Finish on final blank. States: WXYZ are functional states A-J carry 0-9 left K-T carry 0-9 right and add it to the next digit over. Q is final state. (0000R Scan past 0-9 to right, stopping at '+' (0110R (0220R (0330R (0440R (0550R (0660R (0770R (0880R (0990R (0++XL Found '+' -- extend it to left, recording that digit. (X++XL X: Scan left thru +s, then grab a digit. (X0+AR Reinstate plus and remember digit in A/B state. (X1+BR (X2+CR (X3+DR (X4+ER (X5+FR (X6+GR (X7+HR (X8+IR (X9+JR (A++AR Head right to second number and past to end of digits. (A00AR A == '0' (A11AR (A22AR (A33AR (A44AR (A55AR (A66AR (A77AR (A88AR (A99AR (A aL Stop and reverse (states a-j) at end. (AAAaL (ABBaL (ACCaL (ADDaL (AEEaL (AFFaL (AGGaL (AHHaL (AIIaL (AJJaL (a0AYL Add fetched digit to what's there. (a1BYL (a2CYL (a3DYL (a4EYL (a5FYL (a6GYL (a7HYL (a8IYL (a9JYL (a+AXL Adding new digit - go back for more (B++BR Head right to second number and past to end of digits. (B00BR A == '0' (B11BR (B22BR (B33BR (B44BR (B55BR (B66BR (B77BR (B88BR (B99BR (B bL Stop and reverse (states a-j) at end. (BAAbL (BBBbL (BCCbL (BDDbL (BEEbL (BFFbL (BGGbL (BHHbL (BIIbL (BJJbL (b0BYL Add fetched digit to what's there. (b1CYL (b2DYL (b3EYL (b4FYL (b5GYL (b6HYL (b7IYL (b8JYL (b9AWL And carry a 1 (b+BXL Adding new digit -- go back for more (C++CR Head right to second number and past to end of digits. (C00CR A == '0' (C11CR (C22CR (C33CR (C44CR (C55CR (C66CR (C77CR (C88CR (C99CR (C cL Stop and reverse (states a-j) at end. (CAAcL (CBBcL (CCCcL (CDDcL (CEEcL (CFFcL (CGGcL (CHHcL (CIIcL (CJJcL (c0CYL Add fetched digit to what's there. (c1DYL (c2EYL (c3FYL (c4GYL (c5HYL (c6IYL (c7JYL (c8AWL (c9BWL (c+CXL Adding new digit -- go back for more (D++DR Head right to second number and past to end of digits. (D00DR A == '0' (D11DR (D22DR (D33DR (D44DR (D55DR (D66DR (D77DR (D88DR (D99DR (D dL Stop and reverse (states a-j) at end. (DAAdL (DBBdL (DCCdL (DDDdL (DEEdL (DFFdL (DGGdL (DHHdL (DIIdL (DJJdL (d0DYL Add fetched digit to what's there. (d1EYL (d2FYL (d3GYL (d4HYL (d5IYL (d6JYL (d7AWL (d8BWL (d9CWL (d+DXL Adding new digit -- go back for more (E++ER Head right to second number and past to end of digits. (E00ER A == '0' (E11ER (E22ER (E33ER (E44ER (E55ER (E66ER (E77ER (E88ER (E99ER (E eL Stop and reverse (states a-j) at end. (EAAeL (EBBeL (ECCeL (EDDeL (EEEeL (EFFeL (EGGeL (EHHeL (EIIeL (EJJeL (e0EYL Add fetched digit to what's there. (e1FYL (e2GYL (e3HYL (e4IYL (e5JYL (e6AWL (e7BWL (e8CWL (e9DWL (e+EXL Adding new digit -- go back for more (F++FR Head right to second number and past to end of digits. (F00FR A == '0' (F11FR (F22FR (F33FR (F44FR (F55FR (F66FR (F77FR (F88FR (F99FR (F fL Stop and reverse (states a-j) at end. (FAAfL (FBBfL (FCCfL (FDDfL (FEEfL (FFFfL (FGGfL (FHHfL (FIIfL (FJJfL (f0FYL Add fetched digit to what's there. (f1GYL (f2HYL (f3IYL (f4JYL (f5AWL (f6BWL (f7CWL (f8DWL (f9EWL (f+FXL Adding new digit -- go back for more (G++GR Head right to second number and past to end of digits. (G00GR A == '0' (G11GR (G22GR (G33GR (G44GR (G55GR (G66GR (G77GR (G88GR (G99GR (G gL Stop and reverse (states a-j) at end. (GAAgL (GBBgL (GCCgL (GDDgL (GEEgL (GFFgL (GGGgL (GHHgL (GIIgL (GJJgL (g0GYL Add fetched digit to what's there. (g1HYL (g2IYL (g3JYL (g4AWL (g5BWL (g6CWL (g7DWL (g8EWL (g9FWL (g+GXL Adding new digit -- go back for more (H++HR Head right to second number and past to end of digits. (H00HR A == '0' (H11HR (H22HR (H33HR (H44HR (H55HR (H66HR (H77HR (H88HR (H99HR (H hL Stop and reverse (states a-j) at end. (HAAhL (HBBhL (HCChL (HDDhL (HEEhL (HFFhL (HGGhL (HHHhL (HIIhL (HJJhL (h0HYL Add fetched digit to what's there. (h1IYL (h2JYL (h3AWL (h4BWL (h5CWL (h6DWL (h7EWL (h8FWL (h9GWL (h+HXL Adding new digit -- go back for more (I++IR Head right to second number and past to end of digits. (I00IR A == '0' (I11IR (I22IR (I33IR (I44IR (I55IR (I66IR (I77IR (I88IR (I99IR (I iL Stop and reverse (states a-j) at end. (IAAiL (IBBiL (ICCiL (IDDiL (IEEiL (IFFiL (IGGiL (IHHiL (IIIiL (IJJiL (i0IYL Add fetched digit to what's there. (i1JYL (i2AWL (i3BWL (i4CWL (i5DWL (i6EWL (i7FWL (i8GWL (i9HWL (i+IXL Adding new digit -- go back for more (J++JR Head right to second number and past to end of digits. (J00JR A == '0' (J11JR (J22JR (J33JR (J44JR (J55JR (J66JR (J77JR (J88JR (J99JR (J jL Stop and reverse (states a-j) at end. (JAAjL (JBBjL (JCCjL (JDDjL (JEEjL (JFFjL (JGGjL (JHHjL (JIIjL (JJJjL (j0JYL Add fetched digit to what's there. (j1AWL (j2BWL (j3CWL (j4DWL (j5EWL (j6FWL (j7GWL (j8HWL (j9IWL (j+JXL Adding new digit -- go back for more (W01YL carried through and go back to loop. (W12YL carried through and go back to loop. (W23YL carried through and go back to loop. (W34YL carried through and go back to loop. (W45YL carried through and go back to loop. (W56YL carried through and go back to loop. (W67YL carried through and go back to loop. (W78YL carried through and go back to loop. (W89YL carried through and go back to loop. (W90WL keep carrying that 1! (W+1XL Carried to left end, loop. (Y00YL Y: left past start of 2nd number... (Y11YL (Y22YL (Y33YL (Y44YL (Y55YL (Y66YL (Y77YL (Y88YL (Y99YL (Y++XL Y->X then go back for another digit. (X ZR Must have been looping -- we ran out of digits! (Z+ ZR Clean up '+'s (Z11ZR (Z22ZR (Z33ZR (Z44ZR (Z55ZR (Z66ZR (Z77ZR (Z88ZR (Z99ZR (Z00ZR (ZA0ZR Decode A-J to 0-9 (ZB1ZR (ZC2ZR (ZD3ZR (ZE4ZR (ZF5ZR (ZG6ZR (ZH7ZR (ZI8ZR (ZJ9ZR (Z Q0 Halt to right of final digit.