Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The multiplication algorithm I was taught in school was something like this:

  for each digit in the bottom number, starting with the ones digit:
    begin a new line beneath the current state.
    write a number of trailing zeroes equal to the number of digits of the bottom number you've already processed.
    for each digit in the top number, starting with the ones digit:
      write (carry + top digit * bottom digit) % 10 to the left of the leftmost digit on the bottom line of the state.
      the carry for the next digit of the top number will be (carry + top digit * bottom digit) / 10
  use the addition algorithm to compute the sum of all the numbers you wrote this way.
If you hard code it to only handle two digit numbers, it's a bit simpler. It computes the product of two numbers 10A+B, 10C+D for one digit A,B,C,D as (D * B + 10 * D * A) + 10 * (C * B + 10 * C * A). That sounds really confusing, because it is. The visual explanation relates it to something much less confusing in an obvious way.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: