Mathematics Thread

[ben1996123]

so chaos theory is cool and weird

i made a program to simulate langton's ant with different generating sequences and img sizes and stuff and it makes alot of really shitty pictoors but alsó some really cool ones

in particular, RLLR generating sequence makes an infintely (probably) expanding cardioid type thing (notshore if it approaches a perfect cardioid as steps->∞) and it looks really cool

also L^n RR expands arbitrarily slowly as steps->∞ which is cool too, I noticed that L^100 RR stayed bounded within a 12x12 box after 25 billion steps which is weird

Spoiler: RLLR at 10 billion steps

edit:

Spoiler: above image with r=1-cos(theta) layered over it

right half is a pretty good match, left part isnt though, how strange

edit:

LRLRRRRLRL is preddy koo

Spoiler: 200million

 

[brandbest1]

Today I crammed a whole bunch of math, like dot products, cross products, box products, and partial derivatives.

\( \frac{\partial z}{\partial x} \) is very cool!

 

[ben1996123]

Today I crammed a whole bunch of math, like dot products, cross products, box products, and partial derivatives.

\( \frac{\partial z}{\partial x} \) is very cool!

whast is a boxproduct

edit: scalar triple product ok

 

[Smiles]

The monthly economic situation of a manufacturing firm is given by the following equations.

R = 5000x - 10x^2

R[SUB]M[/SUB] = 5000 - 20x

C = 300x + 1/12 x^2

C[SUB]M[/SUB] = 300 + 1/4x^2

where x represents the quantity sold, R represents the firm’s total revenue, RM represents marginal revenue, C represents total cost, and CM represents the marginal cost. All costs are in dollars.
Profit is total revenue minus total cost. What is the firm’s maximum monthly profit?

yeah can someone help me with this one? again the wording is troubling me, not that there's anything wrong with it, but i don't know how to deal with "marginal" stuff.

 

[ben1996123]

The monthly economic situation of a manufacturing firm is given by the following equations.

R = 5000x - 10x^2

R[SUB]M[/SUB] = 5000 - 20x

C = 300x + 1/12 x^2

C[SUB]M[/SUB] = 300 + 1/4x^2

where x represents the quantity sold, R represents the firm’s total revenue, RM represents marginal revenue, C represents total cost, and CM represents the marginal cost. All costs are in dollars.
Profit is total revenue minus total cost. What is the firm’s maximum monthly profit?

yeah can someone help me with this one? again the wording is troubling me, not that there's anything wrong with it, but i don't know how to deal with "marginal" stuff.

isit not just this

Spoiler

\( P=\text{profit}=R-C=5000x-10x^2-300x-\frac{x^2}{12}=4700x-\frac{119x^2}{12} \)
\( \frac{dP}{dx}=4700-\frac{119x}{6}=0 \)
\( x=\frac{28200}{119} \)
\( P=\frac{4700(28200)}{119}-\frac{119(\frac{28200}{119})^2}{12}=556890+\text{abit} \)

 

[Smiles]

isit not just this

Spoiler

\( P=\text{profit}=R-C=5000x-10x^2-300x-\frac{x^2}{12}=4700x-\frac{119x^2}{12} \)
\( \frac{dP}{dx}=4700-\frac{119x}{6}=0 \)
\( x=\frac{28200}{119} \)
\( P=\frac{4700(28200)}{119}-\frac{119(\frac{28200}{119})^2}{12}=556890+\text{abit} \)

thanks for the reply.
but can you explain to me what dP/dx is? i can see at first you divided everything by x but then the denominator changed from 12 to 6 as well.

oh and these were the multiple choice:

a.
$437 003.91
b.
$535 163.26
c.
$415 135.20
d.
$377 125.92

 

[5BLD]

He differentiated P wrt x to find the maximum, aka turning point, aka dP/dx=0 or the quadratic
He didnt do division, he used calculus to find the maximum value

 

[Smiles]

He differentiated P wrt x to find the maximum, aka turning point, aka dP/dx=0 or the quadratic
He didnt do division, he used calculus to find the maximum value

oh okay D:
is his answer right then? cause it doesn't match the multiple choice.
and these tests are known for having the incorrect multiple choice. which one should i choose LOL

 

[ben1996123]

so chaos theory is cool and weird

i made a program to simulate langton's ant with different generating sequences and img sizes and stuff and it makes alot of really shitty pictoors but alsó some really cool ones

in particular, RLLR generating sequence makes an infintely (probably) expanding cardioid type thing (notshore if it approaches a perfect cardioid as steps->∞) and it looks really cool

also L^n RR expands arbitrarily slowly as steps->∞ which is cool too, I noticed that L^100 RR stayed bounded within a 12x12 box after 25 billion steps which is weird

Spoiler: RLLR at 10 billion steps

edit:

Spoiler: above image with r=1-cos(theta) layered over it

right half is a pretty good match, left part isnt though, how strange

edit:

LRLRRRRLRL is preddy koo

Spoiler: 200million

okso tis koo, RLLR stays as a cardioid forever

i maked my program faster and its generated it to over 1 trillion steps (10^12) now

heres the full image after 1 trillion steps (13mb, 10000x10000, cant put on imgur)

 

[CheesecakeCuber]

Can anybody here who is proficient in Python quickly but thoroughly explain to me, wiff a few examples, how to implement karatsuba multiplication in Python? Thanks, much appreciated.

All I can find online are people asking for help because their code is faulty or the explanations are so abstract and littered with code irrelevant to the main task, that I cannot understand it.

 

[5BLD]

Can anybody here who is proficient in Python quickly but thoroughly explain to me, wiff a few examples, how to implement karatsuba multiplication in Python? Thanks, much appreciated.

All I can find online are people asking for help because their code is faulty or the explanations are so abstract and littered with code irrelevant to the main task, that I cannot understand it.

I'm not at my computer but I have written that exact program before. The idea is that you split up your numbers with something like min(len(x),len(y))/2 initially, and then def a karatsuba function that calls itself whenever it needs to multiply. Unless the multiplication is single digit, where the recursing stops. So make a karatsuba(x,y) function and wherever you have a times sign from the formula do karatsuba(whatever two number you have). What exactly are you having trouble with?

PS, you don't want to be multiplying by 10^n or whatever base you're doing, you wanna be using n.zfill(number of zeroes)

 

[F perm]

Can anybody here who is proficient in Python quickly but thoroughly explain to me, wiff a few examples, how to implement karatsuba multiplication in Python? Thanks, much appreciated.

All I can find online are people asking for help because their code is faulty or the explanations are so abstract and littered with code irrelevant to the main task, that I cannot understand it.

Alright, this is poorly done, but it works just fine and stays true to the alg:
EDIT: I changed m from min(len(str(x)), len(str(y))) to min(len(str(x)), len(str(y))) // 2 because every time I used it I did m // 2. I also changed a little in the final return.

Spoiler: v1.1

"""fperm 8/6/2013
Karatsuba algorithm."""

def karatsuba(x, y):
    """Multiplies x and y using the karatsuba alg."""
    
    if x < 10 or y < 10:
        return x * y
    m = min(len(str(x)), len(str(y))) // 2
    zfillNum = max(len(str(x)), len(str(y)))
    x0, y0 = int(str(x).zfill(zfillNum)[m:]), \
             int(str(y).zfill(zfillNum)[m:])
    x1, y1 = int(str(x).zfill(zfillNum)[:m]), \
             int(str(y).zfill(zfillNum)[:m])
    z0 = karatsuba(x0, y0)
    z2 = karatsuba(x1, y1)
    z1 = karatsuba((x0 + x1), (y0 + y1)) - z2 - z0
    return z2 * (100 ** (zfillNum- m)) + \
           z1 * (10 ** (zfillNum- m)) + z0
    
print(karatsuba(12345, 6789))

Spoiler: v1

"""fperm 8/6/2013
Karatsuba algorithm."""

def karatsuba(x, y):
    """Multiplies x and y using the karatsuba alg."""
    
    if x < 10 or y < 10:
        return x * y
    m = min(len(str(x)), len(str(y)))
    zfillNum = max(len(str(x)), len(str(y)))
    x0, y0 = int(str(x).zfill(zfillNum)[m // 2:]), \
             int(str(y).zfill(zfillNum)[m // 2:])
    x1, y1 = int(str(x).zfill(zfillNum)[:m // 2]), \
             int(str(y).zfill(zfillNum)[:m // 2])
    z0 = karatsuba(x0, y0)
    z2 = karatsuba(x1, y1)
    z1 = karatsuba((x0 + x1), (y0 + y1)) - z2 - z0
    return z2 * (10 ** (2 * (zfillNum- m // 2))) + \
           z1 * (10 ** (zfillNum- m // 2)) + z0
    
print(karatsuba(12345, 6789))

Type karatsuba(x, y), and it will return x * y done using the karastsuba alg.

First it checks to see if one of the numbers is one digit, and returns a simple x * y if they are. Then, using min() and len() like 5BLD said, it gives you the length of the smaller number, in this case 4, for m. zfillNum is the length of the larger number, used for zfill purposes. (Quick sidenote on zfill if you don't know what it is. str.zfill(x) will take str and if it is numeric, add 0's to the left until it is x digits long. Doc page.)

x0 and y0 are the back halves of x and y, here 345 and 789. m // 2 (now m) and zfill are used to format them correctly. There is almost definitely a better way to do this, I am not a professional programmer.(m // 2 == m / 2 when m is even, but m / 2 + .5 when m is odd.)

x1 and y1 are the front halves of x and y, formatted in the same way.
z0, z1 and z2 are numbers used in the final calculation. You will notice that they contain calls to karatsuba. This is where the recursion comes into play. Hopefully you understand recursion already, if not, happy reading!(There is also an easter egg in Google about recursion.)

Finally, when all values of z0, z1 and z2 have been calculated and the recursion 'level' is back to the first run through, it returns the answer, once again using zfillNum and m.

I just found out what Karatsuba was yesterday, so you will have to excuse the less than perfect code. Here is where I found my info:

• Mathworld
• I could have used any calculator to check my answers, but I could have used this one which also uses karatsuba
• Good old wikipedia
• And this pdf has info on Karatsuba and other multiplication tricks

If you have any questions on the code, feel free to ask me.

Hey I just noticed when reading backwards in this thread that a bunch of people are doing Project Euler. Me too! I started only like a week ago though. Here is my friend key if anyone wants: 63986219508625_f04d170010c1ee31653dc21faa81ca81

 

[CheesecakeCuber]

I'm not at my computer but I have written that exact program before. The idea is that you split up your numbers with something like min(len(x),len(y))/2 initially, and then def a karatsuba function that calls itself whenever it needs to multiply. Unless the multiplication is single digit, where the recursing stops. So make a karatsuba(x,y) function and wherever you have a times sign from the formula do karatsuba(whatever two number you have). What exactly are you having trouble with?

PS, you don't want to be multiplying by 10^n or whatever base you're doing, you wanna be using n.zfill(number of zeroes)

Thanks for the reply Alex, I have one main problem:

Understanding how to split the big numbers. (Bases and padding wiff zeroes-)

 

[5BLD]

Thanks for the reply Alex, I have one main problem:

Understanding how to split the big numbers. (Bases and padding wiff zeroes-)

Note: "tooming" is the same as "karatsubaring" here. This is because this is an old program, I later tried to generalise it using the Toom-Cook alg.

Spoiler: code and explanation

def splita(st,c):
>sr=str(st)
>return [sr[0:len(sr)-c],sr[len(sr)-c:len(sr)]]

def toomulti1(t,g):
>print "tooming"
>w=min(len(str(t))/2,len(str(g))/2)
>try:
>>a=int(splita(t,w)[0])
>>b=int(splita(t,w)[1])
>>c=int(splita(g,w)[0])
>>d=int(splita(g,w)[1])
>except:
>>return t*g
>p=toomulti1(a,c)
>r=toomulti(b,d)
>try:
>>q=toomulti1((a+b),(c+d))-p-r
>except:
>>q=(a+b)*(c+d)-p-r
>return addzeros(p,2*w)+addzeros(q,w)+r

In english:
def splita(number[string], some quantity c):
>if the input isnt a string it is now
>return part 1, part 2 where the second part is the length of quantity c
>this will fail if the second part is empty, i.e. c=0

def toomulti1(number x, number y):
>show that the computer is doing work
>w is half the minimum length of (x,y) when written in base 10
>Stop doing this if w is 0:
>>a= first part of x
>>b= second part of x
>>c= first part of y
>>d= second part of y
>If stopped; can't split this means that one of the numbers has 1 digit:
>>do naive multiplication
>p= a*c, the first coefficient- this is worked out using the same function
>r= b*d, the last coefficient- this is worked out using the same function
>try to do the formula by
>>doing this whole algorithm again.
>If one of a+b,c+d has one digit this will fail. If this happens, then
>>just do the normal formula, q= (a+b)*(c+d)-p-r using naive multiplication
>return the sum of all of this stuff:
>>pad p with 2*w zeroes (this is obvious due to the formula)
>>pad q with w zeroes
>>r

here are four logs from my program:

Spoiler: 42 * 39

trying to multiply 42 and 39
the minimum half-length of these two numbers is 1
42 is split into 4 and 2
39 is split into 3 and 9
a is 4, b is 2, c is 3, d is 9
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 4 and 3
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 3 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 12
------
trying to multiply 2 and 9
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 9 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 18
now to work out the middle coefficient...
a+b = 6 and c+d = 12
going to do 6*12 using karatsuba multiplication
------
trying to multiply 6 and 12
the minimum half-length of these two numbers is 0
couldn't split because one of 6 and 12 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 72
padded 12 with zeroes to become 1200
padded 42 with zeroes to become 420
this multiplication is finished, the answer is 1638
padded 12 with zeroes to become 1200
padded 42 with zeroes to become 420
and so the answer is 1638

Spoiler: 230948745 * 129387129838

trying to multiply 230948745 and 129387129838
the minimum half-length of these two numbers is 4
230948745 is split into 23094 and 8745
129387129838 is split into 12938712 and 9838
a is 23094, b is 8745, c is 12938712, d is 9838
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 23094 and 12938712
the minimum half-length of these two numbers is 2
23094 is split into 230 and 94
12938712 is split into 129387 and 12
a is 230, b is 94, c is 129387, d is 12
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 230 and 129387
the minimum half-length of these two numbers is 1
230 is split into 23 and 0
129387 is split into 12938 and 7
a is 23, b is 0, c is 12938, d is 7
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 23 and 12938
the minimum half-length of these two numbers is 1
23 is split into 2 and 3
12938 is split into 1293 and 8
a is 2, b is 3, c is 1293, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 2 and 1293
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 1293 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 2586
------
trying to multiply 3 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 24
now to work out the middle coefficient...
a+b = 5 and c+d = 1301
going to do 5*1301 using karatsuba multiplication
------
trying to multiply 5 and 1301
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 1301 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 6505
padded 2586 with zeroes to become 258600
padded 3895 with zeroes to become 38950
this multiplication is finished, the answer is 297574
padded 2586 with zeroes to become 258600
padded 3895 with zeroes to become 38950
------
trying to multiply 0 and 7
the minimum half-length of these two numbers is 0
couldn't split because one of 0 and 7 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 0
now to work out the middle coefficient...
a+b = 23 and c+d = 12945
going to do 23*12945 using karatsuba multiplication
------
trying to multiply 23 and 12945
the minimum half-length of these two numbers is 1
23 is split into 2 and 3
12945 is split into 1294 and 5
a is 2, b is 3, c is 1294, d is 5
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 2 and 1294
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 1294 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 2588
------
trying to multiply 3 and 5
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 5 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 15
now to work out the middle coefficient...
a+b = 5 and c+d = 1299
going to do 5*1299 using karatsuba multiplication
------
trying to multiply 5 and 1299
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 1299 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 6495
padded 2588 with zeroes to become 258800
padded 3892 with zeroes to become 38920
this multiplication is finished, the answer is 297735
padded 2588 with zeroes to become 258800
padded 3892 with zeroes to become 38920
padded 297574 with zeroes to become 29757400
padded 161 with zeroes to become 1610
this multiplication is finished, the answer is 29759010
padded 297574 with zeroes to become 29757400
padded 161 with zeroes to become 1610
------
trying to multiply 94 and 12
the minimum half-length of these two numbers is 1
94 is split into 9 and 4
12 is split into 1 and 2
a is 9, b is 4, c is 1, d is 2
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 9 and 1
the minimum half-length of these two numbers is 0
couldn't split because one of 9 and 1 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 9
------
trying to multiply 4 and 2
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 2 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 8
now to work out the middle coefficient...
a+b = 13 and c+d = 3
going to do 13*3 using karatsuba multiplication
------
trying to multiply 13 and 3
the minimum half-length of these two numbers is 0
couldn't split because one of 13 and 3 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 39
padded 9 with zeroes to become 900
padded 22 with zeroes to become 220
this multiplication is finished, the answer is 1128
padded 9 with zeroes to become 900
padded 22 with zeroes to become 220
now to work out the middle coefficient...
a+b = 324 and c+d = 129399
going to do 324*129399 using karatsuba multiplication
------
trying to multiply 324 and 129399
the minimum half-length of these two numbers is 1
324 is split into 32 and 4
129399 is split into 12939 and 9
a is 32, b is 4, c is 12939, d is 9
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 32 and 12939
the minimum half-length of these two numbers is 1
32 is split into 3 and 2
12939 is split into 1293 and 9
a is 3, b is 2, c is 1293, d is 9
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 3 and 1293
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 1293 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 3879
------
trying to multiply 2 and 9
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 9 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 18
now to work out the middle coefficient...
a+b = 5 and c+d = 1302
going to do 5*1302 using karatsuba multiplication
------
trying to multiply 5 and 1302
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 1302 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 6510
padded 3879 with zeroes to become 387900
padded 2613 with zeroes to become 26130
this multiplication is finished, the answer is 414048
padded 3879 with zeroes to become 387900
padded 2613 with zeroes to become 26130
------
trying to multiply 4 and 9
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 9 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 36
now to work out the middle coefficient...
a+b = 36 and c+d = 12948
going to do 36*12948 using karatsuba multiplication
------
trying to multiply 36 and 12948
the minimum half-length of these two numbers is 1
36 is split into 3 and 6
12948 is split into 1294 and 8
a is 3, b is 6, c is 1294, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 3 and 1294
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 1294 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 3882
------
trying to multiply 6 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 6 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 48
now to work out the middle coefficient...
a+b = 9 and c+d = 1302
going to do 9*1302 using karatsuba multiplication
------
trying to multiply 9 and 1302
the minimum half-length of these two numbers is 0
couldn't split because one of 9 and 1302 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 11718
padded 3882 with zeroes to become 388200
padded 7788 with zeroes to become 77880
this multiplication is finished, the answer is 466128
padded 3882 with zeroes to become 388200
padded 7788 with zeroes to become 77880
padded 414048 with zeroes to become 41404800
padded 52044 with zeroes to become 520440
this multiplication is finished, the answer is 41925276
padded 414048 with zeroes to become 41404800
padded 52044 with zeroes to become 520440
padded 29759010 with zeroes to become 297590100000
padded 12165138 with zeroes to become 1216513800
this multiplication is finished, the answer is 298806614928
padded 29759010 with zeroes to become 297590100000
padded 12165138 with zeroes to become 1216513800
------
trying to multiply 8745 and 9838
the minimum half-length of these two numbers is 2
8745 is split into 87 and 45
9838 is split into 98 and 38
a is 87, b is 45, c is 98, d is 38
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 87 and 98
the minimum half-length of these two numbers is 1
87 is split into 8 and 7
98 is split into 9 and 8
a is 8, b is 7, c is 9, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 8 and 9
the minimum half-length of these two numbers is 0
couldn't split because one of 8 and 9 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 72
------
trying to multiply 7 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 7 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 56
now to work out the middle coefficient...
a+b = 15 and c+d = 17
going to do 15*17 using karatsuba multiplication
------
trying to multiply 15 and 17
the minimum half-length of these two numbers is 1
15 is split into 1 and 5
17 is split into 1 and 7
a is 1, b is 5, c is 1, d is 7
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 1 and 1
the minimum half-length of these two numbers is 0
couldn't split because one of 1 and 1 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 1
------
trying to multiply 5 and 7
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 7 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 35
now to work out the middle coefficient...
a+b = 6 and c+d = 8
going to do 6*8 using karatsuba multiplication
------
trying to multiply 6 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 6 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 48
padded 1 with zeroes to become 100
padded 12 with zeroes to become 120
this multiplication is finished, the answer is 255
padded 1 with zeroes to become 100
padded 12 with zeroes to become 120
padded 72 with zeroes to become 7200
padded 127 with zeroes to become 1270
this multiplication is finished, the answer is 8526
padded 72 with zeroes to become 7200
padded 127 with zeroes to become 1270
------
trying to multiply 45 and 38
the minimum half-length of these two numbers is 1
45 is split into 4 and 5
38 is split into 3 and 8
a is 4, b is 5, c is 3, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 4 and 3
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 3 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 12
------
trying to multiply 5 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 40
now to work out the middle coefficient...
a+b = 9 and c+d = 11
going to do 9*11 using karatsuba multiplication
------
trying to multiply 9 and 11
the minimum half-length of these two numbers is 0
couldn't split because one of 9 and 11 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 99
padded 12 with zeroes to become 1200
padded 47 with zeroes to become 470
this multiplication is finished, the answer is 1710
padded 12 with zeroes to become 1200
padded 47 with zeroes to become 470
now to work out the middle coefficient...
a+b = 132 and c+d = 136
going to do 132*136 using karatsuba multiplication
------
trying to multiply 132 and 136
the minimum half-length of these two numbers is 1
132 is split into 13 and 2
136 is split into 13 and 6
a is 13, b is 2, c is 13, d is 6
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 13 and 13
the minimum half-length of these two numbers is 1
13 is split into 1 and 3
13 is split into 1 and 3
a is 1, b is 3, c is 1, d is 3
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 1 and 1
the minimum half-length of these two numbers is 0
couldn't split because one of 1 and 1 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 1
------
trying to multiply 3 and 3
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 3 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 9
now to work out the middle coefficient...
a+b = 4 and c+d = 4
going to do 4*4 using karatsuba multiplication
------
trying to multiply 4 and 4
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 4 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 16
padded 1 with zeroes to become 100
padded 6 with zeroes to become 60
this multiplication is finished, the answer is 169
padded 1 with zeroes to become 100
padded 6 with zeroes to become 60
------
trying to multiply 2 and 6
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 6 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 12
now to work out the middle coefficient...
a+b = 15 and c+d = 19
going to do 15*19 using karatsuba multiplication
------
trying to multiply 15 and 19
the minimum half-length of these two numbers is 1
15 is split into 1 and 5
19 is split into 1 and 9
a is 1, b is 5, c is 1, d is 9
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 1 and 1
the minimum half-length of these two numbers is 0
couldn't split because one of 1 and 1 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 1
------
trying to multiply 5 and 9
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 9 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 45
now to work out the middle coefficient...
a+b = 6 and c+d = 10
going to do 6*10 using karatsuba multiplication
------
trying to multiply 6 and 10
the minimum half-length of these two numbers is 0
couldn't split because one of 6 and 10 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 60
padded 1 with zeroes to become 100
padded 14 with zeroes to become 140
this multiplication is finished, the answer is 285
padded 1 with zeroes to become 100
padded 14 with zeroes to become 140
padded 169 with zeroes to become 16900
padded 104 with zeroes to become 1040
this multiplication is finished, the answer is 17952
padded 169 with zeroes to become 16900
padded 104 with zeroes to become 1040
padded 8526 with zeroes to become 85260000
padded 7716 with zeroes to become 771600
this multiplication is finished, the answer is 86033310
padded 8526 with zeroes to become 85260000
padded 7716 with zeroes to become 771600
now to work out the middle coefficient...
a+b = 31839 and c+d = 12948550
going to do 31839*12948550 using karatsuba multiplication
------
trying to multiply 31839 and 12948550
the minimum half-length of these two numbers is 2
31839 is split into 318 and 39
12948550 is split into 129485 and 50
a is 318, b is 39, c is 129485, d is 50
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 318 and 129485
the minimum half-length of these two numbers is 1
318 is split into 31 and 8
129485 is split into 12948 and 5
a is 31, b is 8, c is 12948, d is 5
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 31 and 12948
the minimum half-length of these two numbers is 1
31 is split into 3 and 1
12948 is split into 1294 and 8
a is 3, b is 1, c is 1294, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 3 and 1294
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 1294 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 3882
------
trying to multiply 1 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 1 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 8
now to work out the middle coefficient...
a+b = 4 and c+d = 1302
going to do 4*1302 using karatsuba multiplication
------
trying to multiply 4 and 1302
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 1302 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 5208
padded 3882 with zeroes to become 388200
padded 1318 with zeroes to become 13180
this multiplication is finished, the answer is 401388
padded 3882 with zeroes to become 388200
padded 1318 with zeroes to become 13180
------
trying to multiply 8 and 5
the minimum half-length of these two numbers is 0
couldn't split because one of 8 and 5 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 40
now to work out the middle coefficient...
a+b = 39 and c+d = 12953
going to do 39*12953 using karatsuba multiplication
------
trying to multiply 39 and 12953
the minimum half-length of these two numbers is 1
39 is split into 3 and 9
12953 is split into 1295 and 3
a is 3, b is 9, c is 1295, d is 3
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 3 and 1295
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 1295 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 3885
------
trying to multiply 9 and 3
the minimum half-length of these two numbers is 0
couldn't split because one of 9 and 3 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 27
now to work out the middle coefficient...
a+b = 12 and c+d = 1298
going to do 12*1298 using karatsuba multiplication
------
trying to multiply 12 and 1298
the minimum half-length of these two numbers is 1
12 is split into 1 and 2
1298 is split into 129 and 8
a is 1, b is 2, c is 129, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 1 and 129
the minimum half-length of these two numbers is 0
couldn't split because one of 1 and 129 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 129
------
trying to multiply 2 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 16
now to work out the middle coefficient...
a+b = 3 and c+d = 137
going to do 3*137 using karatsuba multiplication
------
trying to multiply 3 and 137
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 137 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 411
padded 129 with zeroes to become 12900
padded 266 with zeroes to become 2660
this multiplication is finished, the answer is 15576
padded 129 with zeroes to become 12900
padded 266 with zeroes to become 2660
padded 3885 with zeroes to become 388500
padded 11664 with zeroes to become 116640
this multiplication is finished, the answer is 505167
padded 3885 with zeroes to become 388500
padded 11664 with zeroes to become 116640
padded 401388 with zeroes to become 40138800
padded 103739 with zeroes to become 1037390
this multiplication is finished, the answer is 41176230
padded 401388 with zeroes to become 40138800
padded 103739 with zeroes to become 1037390
------
trying to multiply 39 and 50
the minimum half-length of these two numbers is 1
39 is split into 3 and 9
50 is split into 5 and 0
a is 3, b is 9, c is 5, d is 0
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 3 and 5
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 5 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 15
------
trying to multiply 9 and 0
the minimum half-length of these two numbers is 0
couldn't split because one of 9 and 0 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 0
now to work out the middle coefficient...
a+b = 12 and c+d = 5
going to do 12*5 using karatsuba multiplication
------
trying to multiply 12 and 5
the minimum half-length of these two numbers is 0
couldn't split because one of 12 and 5 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 60
padded 15 with zeroes to become 1500
padded 45 with zeroes to become 450
this multiplication is finished, the answer is 1950
padded 15 with zeroes to become 1500
padded 45 with zeroes to become 450
now to work out the middle coefficient...
a+b = 357 and c+d = 129535
going to do 357*129535 using karatsuba multiplication
------
trying to multiply 357 and 129535
the minimum half-length of these two numbers is 1
357 is split into 35 and 7
129535 is split into 12953 and 5
a is 35, b is 7, c is 12953, d is 5
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 35 and 12953
the minimum half-length of these two numbers is 1
35 is split into 3 and 5
12953 is split into 1295 and 3
a is 3, b is 5, c is 1295, d is 3
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 3 and 1295
the minimum half-length of these two numbers is 0
couldn't split because one of 3 and 1295 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 3885
------
trying to multiply 5 and 3
the minimum half-length of these two numbers is 0
couldn't split because one of 5 and 3 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 15
now to work out the middle coefficient...
a+b = 8 and c+d = 1298
going to do 8*1298 using karatsuba multiplication
------
trying to multiply 8 and 1298
the minimum half-length of these two numbers is 0
couldn't split because one of 8 and 1298 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 10384
padded 3885 with zeroes to become 388500
padded 6484 with zeroes to become 64840
this multiplication is finished, the answer is 453355
padded 3885 with zeroes to become 388500
padded 6484 with zeroes to become 64840
------
trying to multiply 7 and 5
the minimum half-length of these two numbers is 0
couldn't split because one of 7 and 5 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 35
now to work out the middle coefficient...
a+b = 42 and c+d = 12958
going to do 42*12958 using karatsuba multiplication
------
trying to multiply 42 and 12958
the minimum half-length of these two numbers is 1
42 is split into 4 and 2
12958 is split into 1295 and 8
a is 4, b is 2, c is 1295, d is 8
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 4 and 1295
the minimum half-length of these two numbers is 0
couldn't split because one of 4 and 1295 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 5180
------
trying to multiply 2 and 8
the minimum half-length of these two numbers is 0
couldn't split because one of 2 and 8 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 16
now to work out the middle coefficient...
a+b = 6 and c+d = 1303
going to do 6*1303 using karatsuba multiplication
------
trying to multiply 6 and 1303
the minimum half-length of these two numbers is 0
couldn't split because one of 6 and 1303 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 7818
padded 5180 with zeroes to become 518000
padded 2622 with zeroes to become 26220
this multiplication is finished, the answer is 544236
padded 5180 with zeroes to become 518000
padded 2622 with zeroes to become 26220
padded 453355 with zeroes to become 45335500
padded 90846 with zeroes to become 908460
this multiplication is finished, the answer is 46243995
padded 453355 with zeroes to become 45335500
padded 90846 with zeroes to become 908460
padded 41176230 with zeroes to become 411762300000
padded 5065815 with zeroes to become 506581500
this multiplication is finished, the answer is 412268883450
padded 41176230 with zeroes to become 411762300000
padded 5065815 with zeroes to become 506581500
padded 298806614928 with zeroes to become 29880661492800000000
padded 113376235212 with zeroes to become 1133762352120000
this multiplication is finished, the answer is 29881795255238153310
padded 298806614928 with zeroes to become 29880661492800000000
padded 113376235212 with zeroes to become 1133762352120000
and so the answer is 29881795255238153310

Spoiler: 321 * 6

trying to multiply 321 and 6
the minimum half-length of these two numbers is 0
couldn't split because one of 321 and 6 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 1926
and so the answer is 1926

Spoiler: 118118 * 69

trying to multiply 118118 and 69
the minimum half-length of these two numbers is 1
118118 is split into 11811 and 8
69 is split into 6 and 9
a is 11811, b is 8, c is 6, d is 9
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 11811 and 6
the minimum half-length of these two numbers is 0
couldn't split because one of 11811 and 6 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 70866
------
trying to multiply 8 and 9
the minimum half-length of these two numbers is 0
couldn't split because one of 8 and 9 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 72
now to work out the middle coefficient...
a+b = 11819 and c+d = 15
going to do 11819*15 using karatsuba multiplication
------
trying to multiply 11819 and 15
the minimum half-length of these two numbers is 1
11819 is split into 1181 and 9
15 is split into 1 and 5
a is 1181, b is 9, c is 1, d is 5
now we have to multiply a*b and c*d which we apply karatsuba again for
------
trying to multiply 1181 and 1
the minimum half-length of these two numbers is 0
couldn't split because one of 1181 and 1 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 1181
------
trying to multiply 9 and 5
the minimum half-length of these two numbers is 0
couldn't split because one of 9 and 5 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 45
now to work out the middle coefficient...
a+b = 1190 and c+d = 6
going to do 1190*6 using karatsuba multiplication
------
trying to multiply 1190 and 6
the minimum half-length of these two numbers is 0
couldn't split because one of 1190 and 6 has only 1 digit... so lets do the naive algorithm
this multiplication is finished, the answer is 7140
padded 1181 with zeroes to become 118100
padded 5914 with zeroes to become 59140
this multiplication is finished, the answer is 177285
padded 1181 with zeroes to become 118100
padded 5914 with zeroes to become 59140
padded 70866 with zeroes to become 7086600
padded 106347 with zeroes to become 1063470
this multiplication is finished, the answer is 8150142
padded 70866 with zeroes to become 7086600
padded 106347 with zeroes to become 1063470
and so the answer is 8150142

You split the numbers from the end using the minimum value from halving the lengths or your numbers. Sorry if I'm missing what you're trying to ask.

 

[CheesecakeCuber]

Thank you very much Alex. I think I'm understanding it. Your explanation was wonderful and much better than most I found online. I will be writing my own program and testing it, then I will post it here.

Edit: Ok two clarifications to make. I don't unnerstand what line 3 does. Also, am I correct in saying that you pad p with 2 * min. length zeroes and pad q with min length?

Edit2: Okso I kinof unnerstand line 3, but still need a bit of clarifying. I wrote up a quick program really fast. Apologies for stoopid errors.

import time
import math
import os

#Program to multiply using Karatsuba algorithm

def splitString(string,number)
string = str(string)
return [string[0:len(string)-c, string[len(string)-c:len(sr)]]

def karatsubaMulti(x,y)
print "Donut worry, calculations are being performed..."
minLength = min(len(str(x))/2,len(str(y))/2
if str(minLength) <= 1:
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = str(karatsubaMulti(a,c))
coefficient2 = str(karatsubaMulti(b,d))
try:
answer = karatsubaMulti((a+b),(c+d))-coefficent1-coefficent2
except:
answer = (a+b)*(c+d)-coefficient1-coefficient2
return coefficient1.ljust(2*minLength + str(len(answer)),'0') + answer.ljust(minLength + str(len(answer)), '0')

PS, how does one add a spoiler so I don't kill people's browsers?

 

[5BLD]

Yes. Recall the formula (for base 10):
(10a+b)(10c+d)=100p+10q+r
where p=ac, r=bd and q=(a+b)(c+d)-p-r

So if you're multiplying a number that already has 10s in it (which you do when you split up numbers), well you know how many 10s it has. minLength. That's where the 10^2minLength comes from.

-Don't forget yer ":" after def or your program will be upset.
-SplitString(string,number)=> use the "number" variable in your definition!
-Be careful about your variables, don't just copy mine... tell me if you don't get it. "sr" is a variable in my alg.
-Your string index makes no sense, you can't have a tuple index.
-Do count yer brackets or your program, again, will be upset.
-Str(minLength) is always not going to be <= 1. Because it's a string.
-Your coefficients are strings. Be careful when multiplying.
-ljust doesn't work when you've already got 0s on the end.
>>> "80".ljust(2,"0")
'80'
>>> "8".ljust(2,"0")
'80'
-So I just asked it to multiply by 10. You can make this more efficient.

I fixed your code and this code works (once you indent it properly). Spoilers are done with (without the *) [spoiler*][/spoiler*]

Spoiler: Code with everything that doesn't work highlighted

import time
import math
import os

#Program to multiply using Karatsuba algorithm

def splitString(string,number)
string = str(string)
return [string[0:len(string)-c, string[len(string)-c:len(sr)]]

def karatsubaMulti(x,y)
print "Donut worry, calculations are being performed..."
minLength = min(len(str(x))/2,len(str(y))/2
if str(minLength) <= 1:
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = str(karatsubaMulti(a,c))
coefficient2 = str(karatsubaMulti(b,d))
try:
answer = karatsubaMulti((a+b),(c+d))-coefficent1-coefficent2
except:
answer = (a+b)*(c+d)-coefficient1-coefficient2
return coefficient1.ljust(2*minLength + str(len(answer)),'0') + answer.ljust(minLength + str(len(answer)), '0')

Do try fixing it yourself before viewing this code, which does work.

Spoiler: Edited code

import time
import math
import os
import random

#Program to multiply using Karatsuba algorithm

def splitString(string,number):
string = str(string)
return [string[0:len(string)-number], string[len(string)-number:len(string)]]

def karatsubaMulti(x,y):
minLength = min(len(str(x))/2,len(str(y))/2)
if int(minLength) <= 1:
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = str(karatsubaMulti(a,c))
coefficient2 = str(karatsubaMulti(b,d))
print a,b,c,d
try:
answer = karatsubaMulti((a+b),(c+d))-int(coefficent1)-int(coefficent2)
except:
answer = (a+b)*(c+d)-int(coefficient1)-int(coefficient2)
return int(coefficient1)*10**(2*minLength)+int(coefficient2)+int(answer)*10**(minLength)
a,b=random.randint(100,100000),random.randint(100,100000)
for w in range(0,10):
print "-----------"
print "Today, class, we are going to multiply "+str(a)+" and "+str(b)
print "Karatsuba, what's the answer?"
print karatsubaMulti(a,b)
print "The correct answer is "+str(a*b)+" you moron."

Spoiler: Logs (not logarithms)

Today, class, we are going to multiply 90656 and 99192
Karatsuba, what's the answer?
906 56 991 92
8992349952
The correct answer is 8992349952 you moron.
-----------
Today, class, we are going to multiply 4543 and 64503
Karatsuba, what's the answer?
45 43 645 3
293037129
The correct answer is 293037129 you moron.
-----------
Today, class, we are going to multiply 57783 and 71420
Karatsuba, what's the answer?
577 83 714 20
4126861860
The correct answer is 4126861860 you moron.
-----------
Today, class, we are going to multiply 70846 and 68254
Karatsuba, what's the answer?
708 46 682 54
4835522884
The correct answer is 4835522884 you moron.
-----------
Today, class, we are going to multiply 18059 and 41031
Karatsuba, what's the answer?
180 59 410 31
740978829
The correct answer is 740978829 you moron.
-----------
Today, class, we are going to multiply 30897 and 87550
Karatsuba, what's the answer?
308 97 875 50
2705032350
The correct answer is 2705032350 you moron.
-----------
Today, class, we are going to multiply 58822 and 85045
Karatsuba, what's the answer?
588 22 850 45
5002516990
The correct answer is 5002516990 you moron.
-----------
Today, class, we are going to multiply 84455 and 56920
Karatsuba, what's the answer?
844 55 569 20
4807178600
The correct answer is 4807178600 you moron.
-----------
Today, class, we are going to multiply 55882 and 16621
Karatsuba, what's the answer?
558 82 166 21
928814722
The correct answer is 928814722 you moron.
-----------
Today, class, we are going to multiply 89051 and 72391
Karatsuba, what's the answer?
890 51 723 91
6446490941
The correct answer is 6446490941 you moron.

Your program doing 2^1024. When you trust it enough you can sack the teacher and let Karatsuba do the multiplying without having to be checked every time.

Spoiler: 2^1024

-----------
Today, class, we are going to multiply 2 and 2
Karatsuba, what's the answer?
4
The correct answer is 4 you moron.
-----------
Today, class, we are going to multiply 4 and 4
Karatsuba, what's the answer?
16
The correct answer is 16 you moron.
-----------
Today, class, we are going to multiply 16 and 16
Karatsuba, what's the answer?
256
The correct answer is 256 you moron.
-----------
Today, class, we are going to multiply 256 and 256
Karatsuba, what's the answer?
65536
The correct answer is 65536 you moron.
-----------
Today, class, we are going to multiply 65536 and 65536
Karatsuba, what's the answer?
655 36 655 36
4294967296
The correct answer is 4294967296 you moron.
-----------
Today, class, we are going to multiply 4294967296 and 4294967296
Karatsuba, what's the answer?
429 49 429 49
672 96 672 96
42949 67296 42949 67296
110 245 110 245
18446744073709551616
The correct answer is 18446744073709551616 you moron.
-----------
Today, class, we are going to multiply 18446744073709551616 and 18446744073709551616
Karatsuba, what's the answer?
184 46 184 46
744 7 744 7
18446 74407 18446 74407
928 53 928 53
370 95 370 95
516 16 516 16
37095 51616 37095 51616
887 11 887 11
1844674407 3709551616 1844674407 3709551616
555 42 555 42
260 23 260 23
55542 26023 55542 26023
815 65 815 65
340282366920938463463374607431768211456
The correct answer is 340282366920938463463374607431768211456 you moron.
-----------
Today, class, we are going to multiply 340282366920938463463374607431768211456 and 340282366920938463463374607431768211456
Karatsuba, what's the answer?
340 28 340 28
236 69 236 69
34028 23669 34028 23669
576 97 576 97
209 38 209 38
463 46 463 46
20938 46346 20938 46346
672 84 672 84
3402823669 2093846346 3402823669 2093846346
549 66 549 66
700 15 700 15
54966 70015 54966 70015
124 981 124 981
11 5 11 5
337 46 337 46
74 31 74 31
33746 7431 33746 7431
411 77 411 77
768 21 768 21
14 56 14 56
76821 1456 76821 1456
782 77 782 77
3374607431 768211456 3374607431 768211456
414 28 414 28
188 87 188 87
41428 18887 41428 18887
603 15 603 15
34028236692093846346 3374607431768211456 34028236692093846346 3374607431768211456
374 2 374 2
844 12 844 12
37402 84412 37402 84412
121 814 121 814
386 20 386 20
578 2 578 2
38620 57802 38620 57802
964 22 964 22
3740284412 3862057802 3740284412 3862057802
760 23 760 23
422 14 422 14
76023 42214 76023 42214
118 237 118 237
115792089237316195423570985008687907853269984665640564039457584007913129639936
The correct answer is 115792089237316195423570985008687907853269984665640564039457584007913129639936 you moron.
-----------
Today, class, we are going to multiply 115792089237316195423570985008687907853269984665640564039457584007913129639936 and 115792089237316195423570985008687907853269984665640564039457584007913129639936
Karatsuba, what's the answer?
115 79 115 79
208 92 208 92
11579 20892 11579 20892
324 71 324 71
373 16 373 16
195 42 195 42
37316 19542 37316 19542
568 58 568 58
1157920892 3731619542 1157920892 3731619542
488 95 488 95
404 34 404 34
48895 40434 48895 40434
893 29 893 29
357 9 357 9
850 8 850 8
35709 85008 35709 85008
120 717 120 717
687 90 687 90
78 53 78 53
68790 7853 68790 7853
766 43 766 43
3570985008 687907853 3570985008 687907853
425 88 425 88
928 61 928 61
42588 92861 42588 92861
135 449 135 449
11579208923731619542 3570985008687907853 11579208923731619542 3570985008687907853
151 50 151 50
193 93 193 93
15150 19393 15150 19393
345 43 345 43
241 95 241 95
273 95 273 95
24195 27395 24195 27395
515 90 515 90
1515019393 2419527395 1515019393 2419527395
393 45 393 45
467 88 467 88
39345 46788 39345 46788
861 33 861 33
269 98 269 98
466 56 466 56
26998 46656 26998 46656
736 54 736 54
405 64 405 64
39 45 39 45
40564 3945 40564 3945
445 9 445 9
2699846656 4056403945 2699846656 4056403945
675 62 675 62
506 1 506 1
67562 50601 67562 50601
118 163 118 163
758 40 758 40
79 13 79 13
75840 7913 75840 7913
837 53 837 53
129 63 129 63
99 36 99 36
12963 9936 12963 9936
228 99 228 99
7584007913 129639936 7584007913 129639936
771 36 771 36
478 49 478 49
77136 47849 77136 47849
124 985 124 985
11 9 11 9
26998466564056403945 7584007913129639936 26998466564056403945 7584007913129639936
345 82 345 82
474 47 474 47
34582 47447 34582 47447
820 29 820 29
718 60 718 60
438 81 438 81
71860 43881 71860 43881
115 741 115 741
3458247447 7186043881 3458247447 7186043881
106 442 106 442
913 28 913 28
106442 91328 106442 91328
197 770 197 770
115792089237316195423570985008687907853 269984665640564039457584007913129639936 115792089237316195423570985008687907853 269984665640564039457584007913129639936
385 77 385 77
675 48 675 48
38577 67548 38577 67548
106 125 106 125
778 80 778 80
234 88 234 88
77880 23488 77880 23488
101 368 101 368
3857767548 7788023488 3857767548 7788023488
116 457 116 457
910 36 910 36
116457 91036 116457 91036
207 493 207 493
115 49 115 49
929 21 929 21
11549 92921 11549 92921
104 470 104 470
817 54 817 54
77 89 77 89
81754 7789 81754 7789
895 43 895 43
1154992921 817547789 1154992921 817547789
197 25 197 25
407 10 407 10
19725 40710 19725 40710
604 35 604 35
38577675487788023488 1154992921817547789 38577675487788023488 1154992921817547789
397 32 397 32
668 40 668 40
39732 66840 39732 66840
106 572 106 572
960 55 960 55
10 15 10 15
712 77 712 77
96055 71277 96055 71277
167 332 167 332
3973266840 9605571277 3973266840 9605571277
135 788 135 788
381 17 381 17
135788 38117 135788 38117
173 905 173 905
10 78 10 78
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
The correct answer is 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 you moron.
-----------
Today, class, we are going to multiply 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 and 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
Karatsuba, what's the answer?
134 7 134 7
807 92 807 92
13407 80792 13407 80792
941 99 941 99
10 40 10 40
994 25 994 25
10 19 10 19
970 99 970 99
10 69 10 69
99425 97099 99425 97099
196 524 196 524
1340780792 9942597099 1340780792 9942597099
112 833 112 833
778 91 778 91
112833 77891 112833 77891
190 724 190 724
574 2 574 2
499 82 499 82
57402 49982 57402 49982
107 384 107 384
58 46 58 46
12 74 12 74
5846 1274 5846 1274
71 20 71 20
5740249982 58461274 5740249982 58461274
579 87 579 87
112 56 112 56
57987 11256 57987 11256
692 43 692 43
13407807929942597099 5740249982058461274 13407807929942597099 5740249982058461274
191 48 191 48
57 91 57 91
19148 5791 19148 5791
249 39 249 39
200 10 200 10
583 73 583 73
20010 58373 20010 58373
783 83 783 83
1914805791 2001058373 1914805791 2001058373
391 58 391 58
641 64 641 64
39158 64164 39158 64164
103 322 103 322
793 65 793 65
820 59 820 59
79365 82059 79365 82059
161 424 161 424
239 33 239 33
777 23 777 23
23933 77723 23933 77723
101 656 101 656
7936582059 2393377723 7936582059 2393377723
103 299 103 299
597 82 597 82
103299 59782 103299 59782
163 81 163 81
561 44 561 44
372 17 372 17
56144 37217 56144 37217
933 61 933 61
640 30 640 30
64030 735 64030 735
647 65 647 65
5614437217 640300735 5614437217 640300735
625 47 625 47
379 52 379 52
62547 37952 62547 37952
100 499 100 499
79365820592393377723 5614437217640300735 79365820592393377723 5614437217640300735
849 80 849 80
257 81 257 81
84980 25781 84980 25781
110 761 110 761
33 67 33 67
84 58 84 58
3367 8458 3367 8458
118 25 118 25
8498025781 33678458 8498025781 33678458
853 17 853 17
42 39 42 39
85317 4239 85317 4239
895 56 895 56
134078079299425970995740249982058461274 793658205923933777235614437217640300735 134078079299425970995740249982058461274 793658205923933777235614437217640300735
927 73 927 73
10 0 10 0
628 52 628 52
92773 62852 92773 62852
155 625 155 625
233 59 233 59
748 23 748 23
23359 74823 23359 74823
981 82 981 82
10 63 10 63
9277362852 2335974823 9277362852 2335974823
116 133 116 133
376 75 376 75
116133 37675 116133 37675
153 808 153 808
135 46 135 46
871 99 871 99
13546 87199 13546 87199
100 745 100 745
698 76 698 76
20 9 20 9
69876 2009 69876 2009
718 85 718 85
1354687199 698762009 1354687199 698762009
205 34 205 34
492 8 492 8
20534 49208 20534 49208
697 42 697 42
92773628522335974823 1354687199698762009 92773628522335974823 1354687199698762009
941 28 941 28
315 72 315 72
94128 31572 94128 31572
125 700 125 700
203 47 203 47
368 32 368 32
20347 36832 20347 36832
571 79 571 79
9412831572 2034736832 9412831572 2034736832
114 475 114 475
684 4 684 4
114475 68404 114475 68404
182 879 182 879
10 61 10 61
469 76 469 76
801 87 801 87
46976 80187 46976 80187
127 163 127 163
429 81 429 81
669 3 669 3
42981 66903 42981 66903
109 884 109 884
4697680187 4298166903 4697680187 4298166903
899 58 899 58
470 90 470 90
89958 47090 89958 47090
137 48 137 48
427 69 427 69
42769 318 42769 318
430 87 430 87
581 86 581 86
48 60 48 60
58186 4860 58186 4860
630 46 630 46
4276900318 581864860 4276900318 581864860
485 87 485 87
651 78 651 78
48587 65178 48587 65178
113 765 113 765
46976801874298166903 4276900318581864860 46976801874298166903 4276900318581864860
512 53 512 53
702 19 702 19
51253 70219 51253 70219
121 472 121 472
288 0 288 0
317 63 317 63
28800 31763 28800 31763
605 63 605 63
5125370219 2880031763 5125370219 2880031763
800 54 800 54
19 82 19 82
80054 1982 80054 1982
820 36 820 36
508 53 508 53
753 88 753 88
50853 75388 50853 75388
126 241 126 241
281 19 281 19
46 56 46 56
28119 4656 28119 4656
327 75 327 75
5085375388 281194656 5085375388 281194656
536 65 536 65
700 44 700 44
53665 70044 53665 70044
123 709 123 709
994 64 994 64
10 58 10 58
336 49 336 49
99464 33649 99464 33649
133 113 133 113
60 84 60 84
6084 96 6084 96
61 80 61 80
9946433649 6084096 9946433649 6084096
995 25 995 25
10 20 10 20
177 45 177 45
99525 17745 99525 17745
117 270 117 270
5085375388281194656 9946433649006084096 5085375388281194656 9946433649006084096
150 31 150 31
809 3 809 3
15031 80903 15031 80903
959 34 959 34
728 72 728 72
787 52 787 52
72872 78752 72872 78752
151 624 151 624
1503180903 7287278752 1503180903 7287278752
879 4 879 4
596 55 596 55
87904 59655 87904 59655
147 559 147 559
469768018742981669034276900318581864860 50853753882811946569946433649006084096 469768018742981669034276900318581864860 50853753882811946569946433649006084096
520 62 520 62
177 26 177 26
52062 17726 52062 17726
697 88 697 88
257 93 257 93
615 60 615 60
25793 61560 25793 61560
873 53 873 53
5206217726 2579361560 5206217726 2579361560
778 55 778 55
792 86 792 86
77855 79286 77855 79286
157 141 157 141
422 33 422 33
339 67 339 67
42233 33967 42233 33967
762 0 762 0
587 94 587 94
89 56 89 56
58794 8956 58794 8956
677 50 677 50
4223333967 587948956 4223333967 587948956
481 12 481 12
829 23 829 23
48112 82923 48112 82923
131 35 131 35
52062177262579361560 4223333967587948956 52062177262579361560 4223333967587948956
562 85 562 85
511 23 511 23
56285 51123 56285 51123
107 408 107 408
167 31 167 31
16731 516 16731 516
172 47 172 47
5628551123 167310516 5628551123 167310516
579 58 579 58
616 39 616 39
57958 61639 57958 61639
119 597 119 597
134078079299425970995740249982058461274793658205923933777235614437217640300735 46976801874298166903427690031858186486050853753882811946569946433649006084096 134078079299425970995740249982058461274793658205923933777235614437217640300735 46976801874298166903427690031858186486050853753882811946569946433649006084096
181 5 181 5
488 11 488 11
18105 48811 18105 48811
669 16 669 16
737 24 737 24
137 89 137 89
73724 13789 73724 13789
875 13 875 13
1810548811 7372413789 1810548811 7372413789
918 29 918 29
626 0 626 0
91829 62600 91829 62600
154 429 154 429
916 79 916 79
400 13 400 13
91679 40013 91679 40013
131 692 131 692
916 64 916 64
77 60 77 60
91664 7760 91664 7760
994 24 994 24
10 18 10 18
9167940013 916647760 9167940013 916647760
100 845 100 845
877 73 877 73
100845 87773 100845 87773
188 618 188 618
18105488117372413789 9167940013916647760 18105488117372413789 9167940013916647760
272 73 272 73
428 13 428 13
27273 42813 27273 42813
700 86 700 86
128 90 128 90
615 49 615 49
12890 61549 12890 61549
744 39 744 39
2727342813 1289061549 2727342813 1289061549
401 64 401 64
43 62 43 62
40164 4362 40164 4362
445 26 445 26
844 51 844 51
195 98 195 98
84451 19598 84451 19598
104 49 104 49
674 57 674 57
23 80 23 80
67457 2380 67457 2380
698 37 698 37
8445119598 674572380 8445119598 674572380
911 96 911 96
10 7 10 7
919 78 919 78
91196 91978 91196 91978
183 174 183 174
556 8 556 8
708 66 708 66
55608 70866 55608 70866
126 474 126 474
646 38 646 38
48 31 48 31
64638 4831 64638 4831
694 69 694 69
5560870866 646384831 5560870866 646384831
620 72 620 72
556 97 556 97
62072 55697 62072 55697
117 769 117 769
84451195980674572380 5560870866646384831 84451195980674572380 5560870866646384831
900 12 900 12
66 84 66 84
90012 6684 90012 6684
966 96 966 96
10 62 10 62
732 9 732 9
572 11 572 11
73209 57211 73209 57211
130 420 130 420
9001206684 7320957211 9001206684 7320957211
163 221 163 221
638 95 638 95
163221 63895 163221 63895
227 116 227 116
181054881173724137899167940013916647760 844511959806745723805560870866646384831 181054881173724137899167940013916647760 844511959806745723805560870866646384831
102 55 102 55
668 40 668 40
10255 66840 10255 66840
770 95 770 95
980 46 980 46
10 26 10 26
986 17 986 17
10 3 10 3
98046 98617 98046 98617
196 663 196 663
1025566840 9804698617 1025566840 9804698617
108 302 108 302
654 57 654 57
108302 65457 108302 65457
173 759 173 759
472 88 472 88
108 80 108 80
47288 10880 47288 10880
581 68 581 68
563 3 563 3
25 91 25 91
56303 2591 56303 2591
588 94 588 94
4728810880 563032591 4728810880 563032591
529 18 529 18
434 71 434 71
52918 43471 52918 43471
963 89 963 89
10 52 10 52
10255668409804698617 4728810880563032591 10255668409804698617 4728810880563032591
149 84 149 84
479 29 479 29
14984 47929 14984 47929
629 13 629 13
367 73 367 73
12 8 12 8
36773 1208 36773 1208
379 81 379 81
1498447929 367731208 1498447929 367731208
186 61 186 61
791 37 791 37
18661 79137 18661 79137
977 98 977 98
10 75 10 75
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216
The correct answer is 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216 you moron.

When I remove the dialog yours takes 0.0110027024397s. One thing though is to check no basic errors are causing it to give up early and resort to naive multiplication. Mind you, python actually uses the karatsuba algorithm as its multiplication function.

 

[CheesecakeCuber]

-ljust doesn't work when you've already got 0s on the end.
>>> "80".ljust(2,"0")
'80'
>>> "8".ljust(2,"0")
'80'

I think et does:

Proof

Spoiler

n = str(80)
n.ljust(4,'0')
#prints '8000'
#So mebbe I made a mistake, but the 4 there is the width of string after ljust is used.

Edit1: Ok so I fixed my code and then looked at your modified ver. and it looks more or less correct. I just haff one problem. Nao, the answers are not being printed out on screen. The program appears to be running correctly: It is printing my "calculating line" and recursion appears to be occurring. But, terminal (mac) will then print:

Exit status: 0
logout

[Process completed]
----------------------------------
I believe exit status of zero is good right? And the program supposedly ran without any errors.

Anyway here is the code, but I will still continue to hack at it and try to find my mistake:

Spoiler

import time
import math

#Karatsuba alg is cool

def splitString(string,number):
#Converts "string" variable input to string then splits for Karatsuba
string = str(string)
return [string[0:len(string)-number], string[len(string)-number:len(string)]]

def karatsubaMulti(x,y):
#Where "x" and "y" are your factors
return "Donut worry, calculations are being performed..."
minLength = min(len(str(x))/2,len(str(y))/2)
if int(minLength) <= 1:
#Does naive alg
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = str(karatsubaMulti(a,c))
coefficient2 = str(karatsubaMulti(b,d))
try:
answer = karatsubaMulti((a + b),(c + d)) - int(coefficient1) - int(coefficient2)
except:
answer = (a + b)*(c + d) - int(coefficient1) - int(coefficient2)
return coefficient1.ljust(int(2*minLength) + int(len(answer)),'0') + answer.ljust(int(minLength) + int(len(answer)),'0') + coefficient2

sOne,sTwo = 1234,5678
answer = karatsubaMulti(sOne,sTwo)
print str(answer)

 

[5BLD]

Put a raw_input() at the end to prevent your program from quitting
I'll run your program later though and check.

edit:
>>return "Donut worry, calculations are being performed..."

lol I think you know what you've done

Spoiler

should be print "Donut.." otherwise your program just returns "Donut worry..." as your answer and skips the rest of the alg.

Also sorry to say but your program doesn't work. Because

Spoiler

-answer should be a string
-you are concatenating strings, not ints:
coefficient1.ljust(int(2*minLength),'0') + answer.ljust(int(minLength),'0') + coefficient2

after fixing these I got it to work again.

 

[CheesecakeCuber]

Thanks so much for all your help with my stoopid questions, Alex.

Edit: I swear to God, I think my code is trying to spite me. Now it says that the product is a noneType...and I've already checked for problems with my variables.

Spoiler

import time
import math

#Karatsuba alg is cool

def splitString(string,number):
#Converts "string" variable input to string then splits for Karatsuba
string = str(string)
return [string[0:len(string)-number], string[len(string)-number:len(string)]]

def karatsubaMulti(x,y):
#Where "x" and "y" are your factors
print "Donut worry, calculations are being performed..."
minLength = min(len(str(x))/2,len(str(y))/2)
if int(minLength) <= 1:
#Does naive alg
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = int(karatsubaMulti(a,c))
coefficient2 = int(karatsubaMulti(b,d))
try:
answer = (karatsubaMulti((a + b),(c + d)) - int(coefficient1) - int(coefficient2))
except:
answer = ((a + b)*(c + d) - int(coefficient1) - int(coefficient2))
return coefficient1.ljust(str(2*minLength) + str(len(answer)),'0') + answer.ljust(str(minLength) + str(len(answer)),'0') + coefficient2
ta,tb = 1234,5678
print "We will be multiplying " + str(ta) + " and " + str(tb) + "."
testAnswer = karatsubaMulti(ta,tb)
print "The product is " + str(testAnswer)
time.sleep(15)

 

[5BLD]

Only two mistakes:

Spoiler: You do have problems with your variables

your coefficients (including 'answer') should be strings because you're ljusting them. Also watch out. Don't add strings to get the answer cuz thats concatenating. (aka 123+ 456= 123456)

You're ljusting to 2*minLength+len answer. You know what it should be, I hope

Spoiler: fixed

import time
import math
import random
#Karatsuba alg is cool

def splitString(string,number):
#Converts "string" variable input to string then splits for Karatsuba
string = str(string)
return [string[0:len(string)-number], string[len(string)-number:len(string)]]

def karatsubaMulti(x,y):
#Where "x" and "y" are your factors
minLength = min(len(str(x))/2,len(str(y))/2)
if int(minLength) <= 1:
#Does naive alg
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = str(karatsubaMulti(a,c))
coefficient2 = str(karatsubaMulti(b,d))
try:
answer = str((karatsubaMulti((a + b),(c + d)) - int(coefficient1) - int(coefficient2)))
except:
answer = str(((a + b)*(c + d) - int(coefficient1) - int(coefficient2)))
return int(coefficient1.ljust((int(2*minLength)) + (len(coefficient1)),'0')) + int(answer.ljust(int(minLength) + int(len(answer)),'0')) + int(coefficient2)

k=0
##test 12000 times for errors
for awsiuhfds in range(0,1200):
ta,tb = random.randint(220,20000000),random.randint(220,20000000)
if karatsubaMulti(ta,tb)==ta*tb:
k=k+1
pass
else:
print karatsubaMulti(ta,tb)
print ta*tb
print "----"
raw_input(str(k)+" successes out of 1200.")