CODEWITHSUNDEEP
c++algorithm
maress
maress

Reputation: 3533

Multiplication Algorithm for multipliers of powers of ten

I want to optimize some division algorithm for large numbers, but this is dependent on how fast i can multiply the divisor with powers of ten: divisor * power(10, n) where n is a positive integer. i know about some optimized multiplication algorithms such as the use of FFT, but that still goes though O(nlog(n)), but am looking for something optimized for this case only, otherwise my algorithm performance will have performance greater than O(nlog(n)). Any idea if there is an optimization for this special case?

Note that i intend to implement this in C++.

Upvotes: 0

Views: 654

Answers (1)

discover
discover

Reputation: 46

If you use array to store large numbers, you can copy the divisor to a new array and add n zeros to the end of it. The new array is the the answer you want. The complexity is O(n).

Upvotes: 2

Related Questions