Tag: stack-overflow

Getting a stack overflow error when i submit to canvas but it runs fine in Visual Studio Code, anyone know what the issue is?

Here is the error:

Exception in thread "main" java.lang.StackOverflowError
    at Phi.gcd(Phi.java:14

Here is the assignment:

Euler’s totient function, otherwise known as φ(n), measures the number
of positive integers relatively prime to n that are less than n. Two
numbers are relatively prime if their gcd is 1. For example: φ(9) = 6
because 1, 2, 4, 5, 7, and 8 are relatively prime to 9. More
information about Euler’s totient function can be found at this Wiki
page.

n Relatively Prime    φ(n)
2 1   1
3 1,2 2
4 1,3 2
5 1,2,3,4 4
6 1,5 2
7 1,2,3,4,5,6 6
8 1,3,5,7 4
9 1,2,4,5,7,8 6
10    1,3,7,9 4

Write a function int phi(int n) that takes an integer n as an input
and returns φ(n), and a main() that prompts a user for an integer i,
calls the function φ(i), and prints the result. The upper limit for
the input i is 250000.

The closed form formula for computing φ(n) is: where p1, p2, …, pm
are prime numbers that divide the number n.

The output of your program should look and function like the examples
shown below.

Enter a positive integer n: 8
Phi(n): 4

And here is my code:

import java.util.Scanner;

public class Phi {

    static int gcd(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }

    static int phi(int n) {
        int count=0;
        for(int i = 1; i < n; ++i) {
            if(gcd(n, i) == 1) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter a positive integer n: ");;
        int n = in.nextInt();
        System.out.printf("Phi(%d): %d\n", n, phi(n));
    }

}

Solution:

This is because your recursive GCD method converges to the value of GCD very slowly. For example, if you pass 250000 and 1, your method would use 250000 stack frames, more than most JVMs would allocate for you.

One solution is to rewrite Euclid’s GCD algorithm with iterations. Another solution is to use a faster algorithm:

int gcd(int a, int b) {
    return (b != 0) ? gcd(b, a % b) : a;
}