-----------------------------------

MysticVegeta

Sat Oct 29, 2005 7:06 pm


Prime Factorization Stack Overflow!

-----------------------------------

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?

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

Sat Oct 29, 2005 7:43 pm



-----------------------------------

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


-----------------------------------

MysticVegeta

Sat Oct 29, 2005 10:09 pm



-----------------------------------

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

Sun Oct 30, 2005 12:48 pm


Alex's Opinion

-----------------------------------

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


-----------------------------------

Cervantes

Sun Oct 30, 2005 12:56 pm


Re: Alex's Opinion

-----------------------------------

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

Sun Oct 30, 2005 3:09 pm



-----------------------------------

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

Mon Oct 31, 2005 12:20 am



-----------------------------------

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:

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..  :wink:


-----------------------------------

MysticVegeta

Mon Oct 31, 2005 2:37 pm



-----------------------------------

Thanks a lot!  :D 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

Mon Oct 31, 2005 3:56 pm



-----------------------------------

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


-----------------------------------

MysticVegeta

Mon Oct 31, 2005 6:56 pm



-----------------------------------

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


-----------------------------------

codemage

Wed Nov 02, 2005 8:34 am



-----------------------------------

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

Wed Nov 02, 2005 9:55 am



-----------------------------------

in discrete math we use ~ as negation.


-----------------------------------

MysticVegeta

Thu Nov 03, 2005 7:24 pm



-----------------------------------

whats discrete math? a branch of math?


-----------------------------------

zylum

Sat Nov 05, 2005 12:46 am



-----------------------------------

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


-----------------------------------

MysticVegeta

Sun Nov 06, 2005 4:49 pm



-----------------------------------

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


-----------------------------------

zylum

Mon Nov 07, 2005 10:09 am



-----------------------------------

no. it covers stuff like combinatorics, set theory, logic, probability, trees, recursion... that sort of stuff...