Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'd like to write a simulation of Japanese Multiplication to get benchmarks on large calculations utilizing the shortcut vs traditional CPU multiplication. I'm curious as to whether it makes sense to try this.

enter image description here

My Question: I'd like to know whether or not a software math shortcut, as described above is actually a shortcut at all.

This is a question of programming concept. By utilizing the simulation of Japanese Multiplication, is a program actually capable of improving calculation speed? Or am I doomed from the start?


The answer to this question isn't required to determine whether or not the experiment will succeed, but rather whether or not it's logically possible for such a thing to occur in any program, using this concept as an example.


My theory is that since addition is computed faster than multiplication, a simulation of Japanese multiplication may actually allow a program to multiply (large) numbers faster than the CPU arithmetic unit can. I think this would be a very interesting finding, if it proves to be true.

If, in the multiplication of numbers of any immense size, the shortcut were to calculate the result via less instructions (or faster) than traditional ALU multiplication, I would consider the experiment a success.

share|improve this question
14  
I will immediately and without thinking about the technical details offer you a 100:1 bet that you cannot improve computing speed that way. Algorithms for doing arithmetic are a thoroughly researched topic. There is no chance whatsoever that you're the first person to think of implementing a well-known "manual" algorithm in software. –  Michael Borgwardt May 18 at 10:44
1  
You have ventured onto a professional programmers venue with no apparent understanding or indication of how your question could possibly be relevant, or how it could possibly be answered. I don't think this question belongs here. –  david.pfx May 18 at 11:06
10  
@david.pfx: Programmers (of all stripes, not just professionals) come here to learn things they don't know about, and whether or not software can ever beat hardware is not only relevant to all programmers, it's answerable. –  Blrfl May 18 at 12:09
2  
5  
Please do not cross-post the same question across StackExchange sites. If you feel you have posted in the wrong place then flag for a moderator and we will look into migrating it for you. Thank you. –  maple_shaft May 18 at 20:11

3 Answers 3

This multiplication algorithm does not replace multiplication with addition. Instead, it splits the multiplication into a number of smaller multiplications that are easier for humans to understand. Humans (unlike computers) deal well with patterns and symbols, less so with large numbers (where “large“ means “multiple digits”).

321 × 254

  × |  2E2 +  5E1 +  4E0
----|-------------------
3E2 |  6E4 + 15E3 + 12E2
 +  |   +      +      +
2E1 |  3E3 + 10E2 +  8E1
 +  |   +      +      +
1E0 |  2E2 +  5E1 +  4E0

SUM = 81534

Those weird diagonals in your picture just group the small multiples with the same exponent together, which makes adding easier.

This algorithm can immediately be generalized to the multiplication of big integers, by dividing the input numbers into pieces half the size of native integers. The lower half of an integer is then the “first digit”, the upper half is the carry digit. Remember that a multiplication of two n-bit integers results in a 2n-bit integer, which is why we need that extra space. During addition, possible overflows have to be handled manually (which makes this algorithm inefficient).

So we could apply this algorithm to base 216 or base 232. It is not appropriate to apply this algorithm to base 2: here builtin multiplication will very likely be faster than anything else.

Your “Japanese Multiplication” is just a visual interpretation of lattice multiplication. It suffers from having O(n²) complexity, and faster algorithms exist.

share|improve this answer

Unsurprisingly, you are indeed "doomed from the start".

This "Japanese Multiplication" (which is a visual form of the grid method tought in UK primary schools since the 1990s) has a time complexity of at least O(n^2) where n is the number of digits in the numbers you are multiplying. This is because the number of intersections will be n*n, and you have to deal with each of them.

This is the same as traditional long multiplication.

Toom-Cook-multiplication is about O(n^1.465), and there are better ones by now (their complexity isn't a straight exponential though).

share|improve this answer

...is a program actually capable of improving calculation speed? Or am I doomed from the start?

In pathological cases that are no longer relevant because the environments in which they occurred have fallen into disuse, probably. In practical situations where you're making apples-to-apples comparisons, not on your life.

Look at speed in terms of instruction cycle budget. On Intel CPUs, an integer multiply has a latency of three cycles. That's your budget. Anything you do has to beat that number to be considered an improvement. Three cycles isn't much.

Let's be very generous and go on the assumption that the numbers you're handed are in binary-coded decimal (e.g., the decimal number 1234 is represented as 0x1234). This means that there's no multiplication involved, just logical shifts and AND operations to mask off the digit we want. Those consume one cycle each (less depending on the state of the pipeline, but let's not complicate it). Isolating a digit therefore takes two cycles, storing it someplace to be dealt with later is a third and incrementing the counter for where it's stored is a fourth. The three-cycle budget has been exceeded by 33% just doing the first digits' worth of prep for your shortcut.

Like early CPUs, humans don't have a built-in multiplication instruction, so it has to be done the hard way. If you get good enough with the shortcut, odds are good you'll be able to do large multiplications in fewer mental cycles than doing it the long way. But, as Michael Borgwardt's answer points out, this is still long multiplication that's been optimized to run faster in wetware. CPUs do it in ways that have been optimized to run faster in electrical circuits. Multiplication is a new enough concept that another hundred million years may pass before we evolve groups of neurons that can do it instantly. We probably won't, because we've figured out how to get our machines to do it on our behalf.

share|improve this answer
    
This is not about machine vs. human. CPU instructions work with fixed length integers; they are irrelevant to this question, which is really about working with arbitrary length numbers. And there have been substantial advances in multiplication algorithms as late as 2007. –  Michael Borgwardt May 18 at 13:08
    
@MichaelBorgwardt: What would stop us from developing a CPU that can do arbitrary-length long multiplication in hardware in one instruction if we found a need for it? –  Blrfl May 18 at 13:16
    
@Blrftl: the fact that hardware is just another implementation of an algorithm and the best multiplication algorithm we know is slower than O(n), let alone constant time. Using hardware you can trade space for time by parallel execution, but that doesn't matter unless you postulate self-replicating hardware. –  Michael Borgwardt May 18 at 13:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.