0
\$\begingroup\$

I'm looking at some reference to "On-line arithmetic",in chapter two of this PhD thesis there's a description of such methods. There's a recurrence derived at some point in such thesis that reminds me of the "digit recurrence methods", are they somehow similar?

(Specifically I saw an equation that reminded me of the division by digit recurrence).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ wow, taht's a 196 pages diss. Mind breaking the second chapter a bit down for us? \$\endgroup\$ Commented Aug 24, 2016 at 13:59
  • \$\begingroup\$ Just look at section 2.1. (it's short) \$\endgroup\$ Commented Aug 24, 2016 at 14:10

1 Answer 1

1
\$\begingroup\$

There seems to be substantial difference between on-line arithmetic (as described in your link) and digit recurrence methods (as described here for example). The only resemblance between the two methods is that they are both sequential.

  • on-line arithmetic processes long numbers one digit at a time, without waiting for the whole numbers to be there. For example, if you compute XXX2+YYY3, you know the result will be ZZZ5 without receiving any more digits of X and Y. In the next step, when one extra digit of each operand is available (e.g. XX72+YY53) you will be able to produce one extra result digit, ZZ25.
  • digit recurrence methods use recurrent formulae to implement certain operations like division. They operate on all digits of the operands on every step, but the result becomes more and more precise as the number of steps increases. For example, if I need to compute 123/7, I could conclude after step 1 that the result is 10 and the remainder is 53. In the second step I will further divide my remainder and update my result to be 17 with the remainder 4. If it's the integer division I'm after, that would be my final step.
\$\endgroup\$
3
  • \$\begingroup\$ I'm not sure your description of online arithmetic matches what the thesis I shown says. For instance in your example you start with the less significant digit, while the thesis states that the input is processed from the most significand digits toward the less significant one. Also it would probably be better to show the same operation how it works. \$\endgroup\$ Commented Aug 24, 2016 at 14:33
  • \$\begingroup\$ Also the equation 2.6. in the defintion 2.4. is very similar to the digit recurrence equation. \$\endgroup\$ Commented Aug 24, 2016 at 14:36
  • \$\begingroup\$ @user8469759 it's not totally unexpected, after all any division algorithm will have to satisfy the formula X=D*Q+R. The difference is in what Dj, Qj and Rj represent. \$\endgroup\$ Commented Aug 24, 2016 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.