开发者

Fastest method implementing number multiplication in strings (1000000 digits) [closed]

开发者_运维问答 It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 9 years ago.

I want to write fastest possible algorithm for 2 number multiplications. Each number has max digits around 1000000 and is contained in string.

Anyone want to tell about this problem? I searching really speed solution.


You should convert your string to a binary representation of the number. After that, one of the fastest multiplication algorithms I know of is Karatsuba's.


Just to expand on Pablo's answer, suppose each number is a string 1000008 decimal digits long. You could convert that to be 111112 9-digit decimal numbers, each stored in a UInt32. Do your multiplication algorithm on those. (Note you will have to use UInt64 to hold the result of multiplying two UInt32 sections, so you may want a 64-bit machine.) That should give you a factor of 9^2 or 9^log2(3) speedup over base 10, depending on the algorithm.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜