Algorithm for making problem easy


#1

I am writing code to multiply two big numbers in python . I am using Karatsuba's algorithm.
for this problem . Hence i have to divide these two number in two part without counting individual digits in both of these number . Like if the number is 4567 i can easily divide it in two parts 45 and 67 .But when the number is 3141592653589793238462643383279502884197169399375105820974944592
then i want to avoid counting .Do any body have idea of breaking this number apart in two individual numbers
without counting each single number in this big number .?


#2

Why do you want to avoid counting the number of digits? (I assume that's what you mean)

Breaking it into two is going to take more time than counting, so it would make no significant difference. Counting isn't what's dominating the cost of splitting it in two

Additionally, you have already done the counting if it's a list or string


#3

I know the breaking it takes much time but i just want to experiment with very big number and hence i need very good approach for that .Although i have one but that is not very efficient with respect to time .


#4

Isn't Karatsuba's algorithm kinda old?
I remember there were other ones created that are faster like Schönhage–Strassen algorithm. But I'm not too sure, I didn't really read much into them.


#5

It would only make sense to avoid counting digits if that allows you to do it in less than linear time with regard to the number of digits.

If you're splitting it in worse than linear time, then something else is wrong - because all it takes is to copy from the beginning to the middle into one string, and then from the middle to the end for the other one.

Representing the numbers at all takes linear time. Splitting numbers into two doesn't worsen this - I don't see how you could possibly improve on that


#6

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.