Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

On SuperUser, I asked a (possibly silly) question about processors using mathematical shortcuts and would like to have a look at the possibility at the software application of that concept.

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
    
I'm not suggesting that this would necessarily be an applicable or useful thing, but it would be exciting to illicit such a result from software. What is this concept called? It seems like it would be a form of virtual hardware acceleration, but perhaps that's the wrong term. –  user17734 May 18 at 9:22
    
In general it might be possible that a few instructions would run faster and accomplish exactly the same as one instruction (for instance, I've heard that dec ecx; jnz ... is faster than loop ...), but the trick you have there is unlikely to do that. It replaces one multiplication of large numbers with many multiplications of small numbers. That entails multiplications or table lookups, conditional jumps and probable memory access. If, on the other hand, you're talking about multiplying arbitrarily large integers, then this is merely the most basic way to do it. –  Karolis Juodelė May 18 at 9:59
    
Ok Karolis, I'm a web developer and haven't worked with 9/10 of the vocabulary you used there, but in case I understood anything, did you mean that it might be faster with huge numbers? @KarolisJuodelė –  user17734 May 18 at 10:08
1  
1  
Meta discussion –  Gilles May 18 at 20:31

2 Answers 2

When considering algorithms for multiplying large numbers, the first think to keep in mind is the asymptotic complexity. Generally speaking, algorithms with better (smaller) asymptotic complexity are faster, though this only goes so far. So the first thing to do to find out whether Japanese multiplication is "worthwhile" is to calculate its asymptotic complexity. You have to be careful with respect to the model of computation, but in your case it probably won't make a big difference; probably your algorithm has "bad" asymptotic complexity.

The second thing to notice is that the multiplication logic is already there in the CPU, and no code that you can write will be faster than calling the built-in multiplication instruction. Of course, this is only good for multiplying machine words (or multiwords, in some cases). That means that your algorithm had better take advantage of the multiplication capabilities of your processor. While not affecting the asymptotic complexity, it does considerably affect the constants. All fast multiplication algorithms use machine multiplication instructions.

The best way to know whether the algorithm is any good in practice is to program and optimize it. Use a language like C which produces fast code, and then you can compare it to libraries such as GMP. This is the only convincing way to claim that your algorithm is better than existing ones, though you should expend some effort on optimization.

Finally, you claim that Japanese multiplication is better than CPU multiplication algorithms since it only uses addition. Textbook multiplication algorithm also only use addition, since everything is in binary. But probably this can be optimized further at the expense of using more gates, by having logic for small multiplications. You can look up what algorithms CPUs use, perhaps they're similar to Japanese multiplication.

share|improve this answer

The method shown in the picture is essentially the same as the standard algorithm (long multiplication) taught in many schools. Since this way of doing multiplication is common knowledge, I don't expect it would help you speed up multiplications on a computer... unless you think the idea of performing small multiplications with overlapping lines would somehow be faster than normal circuit design.

To see why this method is the same as long multiplication, let's say we're multiplying abc * def. With Japanese multiplication, you compute five numbers: cf, bf+ce, af+be+cd, ae+bd, and ad. Then you add them together, adding the tens digit of each to the ones digit of the next, to produce the sum cf + 10(bf+ce) + 100(af+be+cd) + 1000(ae+bd) + 10000ad.

Compare this to long multiplication. You first compute the three numbers cf+10bf+100af, ce+10be+100ae, and cd+10bd+100ad. But the second number is shifted to the left by one digit, and the third number by two. So when you add them, you get (cf+10bf+100af)+10(ce+10be+100ae)+100(cd+10bd+100ad), which is equivalent to the answer we got from Japanese multiplication.

share|improve this answer

Your Answer

 
discard

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