# Recursive multiplication and Karatsuba

James Charles

Greenhorn

Posts: 1

posted 4 years ago

- 0

Hey everyone, I've got a question where I'm sort of stuck on writing a java code for a recursive "school method" multiplication where we have input 'n' and two n digit numbers 'a' and 'b' where the output is m=a.b. I also have to use an array representation for representing numbers. Could anyone please help me out? Thanks

The basic format is a=a1.B^(k) + a0 and b=b1.B^(k) + b0 where a.b=a1.b1.B^(2k)+(a1.b0+a0.b1).B^(k)+a0.b0 and k=floor(n/2)

Also then how would you use this and implement a Karatsuba multiplication if say n>3.

The basic format is a=a1.B^(k) + a0 and b=b1.B^(k) + b0 where a.b=a1.b1.B^(2k)+(a1.b0+a0.b1).B^(k)+a0.b0 and k=floor(n/2)

Also then how would you use this and implement a Karatsuba multiplication if say n>3.

Campbell Ritchie

Sheriff

Posts: 47310

52

posted 4 years ago

- 0

Welcome to the Ranch

What is a Karatsuba multiplication? I have never heard of it before.

I am going to have to tell you to use the high-tech hardware I so often recommend. A sheet of paper, a (soft) pencil and a (large) eraser.

Write down how you would do it on paper, and get it down to words of one syllable. Then you will know how to convert it to code. You may have to write passing half a number. Remember you will get down to where

What is a Karatsuba multiplication? I have never heard of it before.

I am going to have to tell you to use the high-tech hardware I so often recommend. A sheet of paper, a (soft) pencil and a (large) eraser.

Write down how you would do it on paper, and get it down to words of one syllable. Then you will know how to convert it to code. You may have to write passing half a number. Remember you will get down to where

*k*is 0, and you will have to stop your recursion at that point.
posted 4 years ago

- 0

James, please BeForthrightWhenCrossPostingToOtherSites

http://www.java-forums.org/new-java/40500-recursive-multiplication-karatsuba.html

http://javaprogrammingforums.com/algorithms-recursion/7920-recursive-multiplication-karatsuba.html

http://www.daniweb.com/software-development/java/threads/353180

http://www.programmersheaven.com/mb/java/422411/422411/recursive-multiplication-and-karatsuba/

http://www.java-forums.org/new-java/40500-recursive-multiplication-karatsuba.html

http://javaprogrammingforums.com/algorithms-recursion/7920-recursive-multiplication-karatsuba.html

http://www.daniweb.com/software-development/java/threads/353180

http://www.programmersheaven.com/mb/java/422411/422411/recursive-multiplication-and-karatsuba/

luck, db
*There are no new questions, but there may be new answers.*

I agree. Here's the link: http://aspose.com/file-tools |