Prime Factorization Stack Overflow!

[MysticVegeta]

I am using the following procedure recursion but if i input in 714768071, i get the stack overflow error, is there a way to bypass it/resolve it?

code:

var ans := "" fcn prime (n : int) : boolean     if n = 2 then         result true     end if     for s : 2 .. n - 1         if n mod s = 0 then             result false         end if     end for     result true end prime proc sol (c : int, n : int)     var check : int     if c > n then         return     end if     if n mod c = 0 then         if prime (c) then             check := n div c             if check = 1 then                 put intstr (c) ..                 return             elsif check = 2 then                 put intstr (c) + "*" ..                 return             else                 put intstr (c) + "*" ..                 if check mod c = 0 then                     sol (c, check)                 else                     sol (c + 1, check)                 end if             end if             check := 0         end if     else         sol (c + 1, n)     end if end sol for x : 1 .. 5     sol (2, Rand.Int (2, 3000))     put "" end for put "" % sol (2, 714768071)

Please help! Thank you

[Cervantes]

Maybe it's not entirely necessary, but it'd help if it were commented.

[MysticVegeta]

code:

var ans := "" fcn prime (n : int) : boolean %Straightforward function, checks whether the function is prime or not     if n = 2 then         result true     end if     for s : 2 .. n - 1         if n mod s = 0 then             result false         end if     end for     result true end prime proc sol (c : int, n : int) %C = divisor, n = number     var check : int     if c > n then %if divisor greater than the number(self explainatory math lol)         return     end if     if n mod c = 0 then %If the divisor divides perfectly into n then         if prime (c) then %Also if the number is prime factor then             check := n div c %Check is num/divisor             if check = 1 then %Say n is 5, divisor is 5, so 5 is a prime factor of 5 and we want the program to return now                 put intstr (c) ..                 return             else                 put intstr (c) + "*" .. %or if check is > 1 (cant be less)                 if check mod c = 0 then %now if check/divisor is perfect number then (ex: prime factors of 100 :                 %2*2*5*5, you see the 2 repeating? So when we get 2 as a prime factor, 100/2=50, 50 is also divisble by 2!                 %so we needn't go to check 3 right now. have to check with 2 again!                     sol (c, check) %n is check instead of n, otherwise we would have 2 as a prime factor and the number                     %will remain 100! So have to make it 50 and make it do the whole thing again.                 else                     sol (c + 1, check) %If divisor wont repeat then we do this for ex: Prime Factors of 10: 2*5. 10/2 = 5                     %5 isnt divisible by 2! so we go to 3 now.                 end if             end if         end if     else         sol (c + 1, n) %if n mod c is not 0 then take the next number     end if end sol for x : 1 .. 5     sol (2, Rand.Int (2, 12354)) %lol random number prime factors     put "" end for put "" % sol (2, 714768071)

[Mr. T]

Does Turing have any other primitive types that can hold quantities larger then int?

[Cervantes]

Pwned wrote:

Does Turing have any other primitive types that can hold quantities larger then int?

natural numbers can go twice as high as integers, but they start at zero. real numbers can go very high.

[MysticVegeta]

I dont know why they put nat as 0 too, in math, nats start at 1. Also knows as counting numbers, but then again, in math ints can go infinite

[zylum]

the reason you are getting stack overflow is because you are recursing too far... you are using up all of the available memory. everytime you recurse forward, you are leaving the current function and going into a new one but the computer has to remember all the values of where you left off and what the values of the variables were. so if you recurse too far you run out of memory.

the main problem with your function is that you are using it to iterate through devisors. this is unecesary because the body of you function can easily deal with this.

heres a better implementation of a prime factor generator:

code:

fcn isPrime (n : int) : boolean     if n mod 2 = 0 and n ~= 2 then         result false     end if     for i : 3 .. round (sqrt (n)) by 2         if n mod i = 0 then             result false         end if     end for     result true end isPrime proc primeFactors (n, depth : int)     put "current depth: ", depth     var d : int := 2     loop         exit when isPrime (n)         if n mod d = 0 then             if isPrime (d) then                 put d, " "                 primeFactors (n div d, depth + 1)                 return             else                 primeFactors (d, depth + 1)                 primeFactors (n div d, depth + 1)                 return             end if         else             d += 1         end if     end loop     put n end primeFactors primeFactors (714768071, 1)

note: i added a depth variable to illustrate how much shallower my recursion was compared to yours. when i added a depth counter to yours, it reached a depth of over 15000...

hope that helps..

[MysticVegeta]

Thanks a lot! works perfect, by the ways, what does (~) mean in the if structure? I have seen that in your maze solution too and i cant find it in the turing reference. thanks a lot again

[beard0]

~ is just a "not" shorthand (thus ~true=false)

[MysticVegeta]

I dont know why they changed the not sign (!) to (~) maybe they wanted to make it different.. (!) is better

[codemage]

Agreed. ! has always meant not in CS.
~ has often used as shorthand for "equivalent", or "roughly equal to" in the circles I've been taught in.

[zylum]

in discrete math we use ~ as negation.

[MysticVegeta]

whats discrete math? a branch of math?

[zylum]

discrete math is probably the most useful branch of math for programming

[MysticVegeta]

Do you mean math for like AI algorithms/other algorithms?