Thread: Euclid Calculator GCD and LCM using BigInteger

I'm trying to make a gui calculator that will find Euclid's GCD and LCM from two number inputs. My problem is that no matter what inputs I enter, the GCD is always giving an output of 0, thus making the LCM divide by zero. If anyone can find the error in my logic, I would greatly appreciate it. I haven't got a lot of experience with BigInteger so :/ Here is my code for my methods gcd and lcm:

public static BigInteger gcd(BigInteger a, BigInteger b){
	while(a.compareTo(b) > 0){
            if (a.compareTo(b) > b.intValue()){
		a.equals(a.mod(b));
            }else{
		b.equals(b.mod(a));
            }
	}
	return a.max(b);
}
 
public static BigInteger lcm(BigInteger a, BigInteger b){
	return ((a.multiply(b)).divide(gcd(a,b)));
}

Thanks for the reply! So how exactly might I fix this? Basically, I started out using integers and am converting to BigInteger. My code for using integers is as follows and I need BigInteger to do what the following code does:

public static int gcd(int a, int b){
		while(a != 0 && b != 0){
			if (a > b){
				a = a % b;
			}else{
				b = b % a;
			}
		}
		return Math.max(a,b);
	}
 
	public static int lcm(int a, int b){
		return (a*b/(gcd(a,b)));
	}

One thing you could try is instead of when transferring to BigInteger

while(a.compareTo(b)>0){

Try comparing it the same way with the integer gcd method. When you say while(a.compareTo(b)>0), you are really saying, "While a is greater than b, keep looping." In you int gcd method, you are saying, "while a does not equal b and b does not equal a, keep looping." See what you did there? Now, to fix your logic, you only have to change the boolean operator to equate to your int method. So, instead of >, you should use != .

Thanks for the reply, aesguitar. I implemented what you suggested which I'm pretty sure was a copy/paste error but now I am getting a new error saying mod is not positive. If it helps I will just paste all of my code for the program and see if anyone can shed some light on it, thanks again.

Code for Euclid.java (mainly the methods):

package euclid;
 
import java.math.BigInteger;
 
/**
 *
 * @author Shane
 */
public class Euclid {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Euclidgui euclid = new Euclidgui();
        euclid.setVisible(true);
    }
 
    public static BigInteger gcd(BigInteger a, BigInteger b) {
        while (a.compareTo(b) != 0) {
            if (a.compareTo(b) > 0) {
                a = a.mod(b);
            } else {
                b = b.mod(a);
            }
        }
        return a.max(b);
    }
 
    public static BigInteger lcm(BigInteger a, BigInteger b) {
        return ((a.multiply(b)).divide(gcd(a, b)));
    }
}

Code for Euclidgui.java (Problem may be in the gui but I'm fairly certain it's not):

package euclid;
 
import java.math.BigInteger;
import javax.swing.JOptionPane;
 
/**
 *
 * @author Shane
 */
public class Euclidgui extends javax.swing.JFrame {
 
    /**
     * Creates new form Euclidgui
     */
    public Euclidgui() {
        initComponents();
    }
 
    /**
     * This method is called from within the constructor to initialize the form.
     * WARNING: Do NOT modify this code. The content of this method is always
     * regenerated by the Form Editor.
     */
    @SuppressWarnings("unchecked")
    // <editor-fold defaultstate="collapsed" desc="Generated Code">                          
    private void initComponents() {
 
        jFormattedTextField1 = new javax.swing.JFormattedTextField();
        jInternalFrame1 = new javax.swing.JInternalFrame();
        jTextField1 = new javax.swing.JTextField();
        input2Text = new javax.swing.JTextField();
        jLabel1 = new javax.swing.JLabel();
        jLabel2 = new javax.swing.JLabel();
        input1Text = new javax.swing.JTextField();
        computeGcdButton = new javax.swing.JButton();
        ResetButton = new javax.swing.JButton();
        lcmButton = new javax.swing.JButton();
        answerLabel = new javax.swing.JLabel();
        jScrollPane1 = new javax.swing.JScrollPane();
        gcdTextAnswer = new javax.swing.JTextPane();
        jLabel3 = new javax.swing.JLabel();
 
        jFormattedTextField1.setText("jFormattedTextField1");
 
        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
 
        jInternalFrame1.setTitle("Greatest Common Divisor");
        jInternalFrame1.setVisible(true);
 
        jTextField1.setText("Greatest Common Divisor Program");
 
        jLabel1.setText("Enter X:");
 
        jLabel2.setText("Enter Y:");
 
        computeGcdButton.setText("Compute gcd(x, y)");
        computeGcdButton.addMouseListener(new java.awt.event.MouseAdapter() {
            public void mouseClicked(java.awt.event.MouseEvent evt) {
                computeGcdButtonMouseClicked(evt);
            }
        });
 
        ResetButton.setText("Reset");
        ResetButton.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                ResetButtonActionPerformed(evt);
            }
        });
 
        lcmButton.setText("Compute lcm(x, y)");
        lcmButton.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                lcmButtonActionPerformed(evt);
            }
        });
 
        answerLabel.setText("gcd(x, y)");
 
        jScrollPane1.setViewportView(gcdTextAnswer);
 
        jLabel3.setText("lcm(x, y)");
 
        javax.swing.GroupLayout jInternalFrame1Layout = new javax.swing.GroupLayout(jInternalFrame1.getContentPane());
        jInternalFrame1.getContentPane().setLayout(jInternalFrame1Layout);
        jInternalFrame1Layout.setHorizontalGroup(
            jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(jInternalFrame1Layout.createSequentialGroup()
                .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addGroup(jInternalFrame1Layout.createSequentialGroup()
                        .addGap(133, 133, 133)
                        .addComponent(jTextField1, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE))
                    .addGroup(jInternalFrame1Layout.createSequentialGroup()
                        .addGap(38, 38, 38)
                        .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING, false)
                            .addGroup(jInternalFrame1Layout.createSequentialGroup()
                                .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                                    .addComponent(computeGcdButton)
                                    .addGroup(jInternalFrame1Layout.createSequentialGroup()
                                        .addComponent(jLabel1)
                                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                                        .addComponent(input1Text, javax.swing.GroupLayout.PREFERRED_SIZE, 120, javax.swing.GroupLayout.PREFERRED_SIZE)))
                                .addGap(42, 42, 42)
                                .addComponent(jLabel2)
                                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                                .addComponent(input2Text, javax.swing.GroupLayout.PREFERRED_SIZE, 121, javax.swing.GroupLayout.PREFERRED_SIZE))
                            .addGroup(jInternalFrame1Layout.createSequentialGroup()
                                .addComponent(answerLabel)
                                .addGap(18, 18, 18)
                                .addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 203, javax.swing.GroupLayout.PREFERRED_SIZE)
                                .addGap(18, 18, 18)
                                .addComponent(jLabel3))
                            .addGroup(jInternalFrame1Layout.createSequentialGroup()
                                .addComponent(lcmButton)
                                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                                .addComponent(ResetButton)
                                .addGap(23, 23, 23)))))
                .addContainerGap(javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE))
        );
        jInternalFrame1Layout.setVerticalGroup(
            jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(jInternalFrame1Layout.createSequentialGroup()
                .addContainerGap()
                .addComponent(jTextField1, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addGap(18, 18, 18)
                .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)
                    .addComponent(input2Text, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
                    .addComponent(jLabel1)
                    .addComponent(jLabel2)
                    .addComponent(input1Text, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE))
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 31, Short.MAX_VALUE)
                .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addGroup(jInternalFrame1Layout.createSequentialGroup()
                        .addComponent(jLabel3)
                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED))
                    .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                        .addGroup(jInternalFrame1Layout.createSequentialGroup()
                            .addComponent(answerLabel)
                            .addGap(54, 54, 54))
                        .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, jInternalFrame1Layout.createSequentialGroup()
                            .addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 160, javax.swing.GroupLayout.PREFERRED_SIZE)
                            .addGap(18, 18, 18))))
                .addComponent(computeGcdButton)
                .addGap(18, 18, 18)
                .addGroup(jInternalFrame1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)
                    .addComponent(lcmButton)
                    .addComponent(ResetButton))
                .addGap(30, 30, 30))
        );
 
        javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
        getContentPane().setLayout(layout);
        layout.setHorizontalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addComponent(jInternalFrame1)
        );
        layout.setVerticalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addComponent(jInternalFrame1)
        );
 
        pack();
    }// </editor-fold>                        
 
    private void computeGcdButtonMouseClicked(java.awt.event.MouseEvent evt) {                                              
        BigInteger input1 = BigInteger.ZERO; 
        BigInteger input2 = BigInteger.ZERO;
 
        try{
            input1 = new BigInteger(input1Text.getText());
        }catch(Exception e){
            JOptionPane.showMessageDialog(this, "Bad X Input", "Error", JOptionPane.ERROR_MESSAGE);
        }
 
        try{
            input2 = new BigInteger(input2Text.getText());
        }catch(Exception e){
            JOptionPane.showMessageDialog(this, "Bad Y Input", "Error", JOptionPane.ERROR_MESSAGE);
        }
 
        BigInteger gcd = Euclid.gcd(input1, input2);
 
        gcdTextAnswer.setText(gcd.toString());
    }                                             
 
    private void lcmButtonActionPerformed(java.awt.event.ActionEvent evt) {                                          
        BigInteger input1 = BigInteger.ZERO;
        BigInteger input2 = BigInteger.ZERO;
 
        try{
            input1 = new BigInteger(input1Text.getText());
        }catch(Exception e){
            JOptionPane.showMessageDialog(this, "Bad X Input", "Error", JOptionPane.ERROR_MESSAGE);
        }
 
        try{
            input2 = new BigInteger(input2Text.getText());
        }catch(Exception e){
            JOptionPane.showMessageDialog(this, "Bad Y Input", "Error", JOptionPane.ERROR_MESSAGE);
        }
 
        BigInteger lcm = Euclid.lcm(input1, input2);
 
        gcdTextAnswer.setText(lcm.toString());
    }                                         
 
    private void ResetButtonActionPerformed(java.awt.event.ActionEvent evt) {                                            
        input1Text.setText("");
        input2Text.setText("");
        gcdTextAnswer.setText("");
    }                                           
 
    /**
     * @param args the command line arguments
     */
    public static void main(String args[]) {
        /* Set the Nimbus look and feel */
        //<editor-fold defaultstate="collapsed" desc=" Look and feel setting code (optional) ">
        /* If Nimbus (introduced in Java SE 6) is not available, stay with the default look and feel.
         * For details see http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html 
         */
        try {
            for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) {
                if ("Nimbus".equals(info.getName())) {
                    javax.swing.UIManager.setLookAndFeel(info.getClassName());
                    break;
                }
            }
        } catch (ClassNotFoundException ex) {
            java.util.logging.Logger.getLogger(Euclidgui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        } catch (InstantiationException ex) {
            java.util.logging.Logger.getLogger(Euclidgui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        } catch (IllegalAccessException ex) {
            java.util.logging.Logger.getLogger(Euclidgui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        } catch (javax.swing.UnsupportedLookAndFeelException ex) {
            java.util.logging.Logger.getLogger(Euclidgui.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
        }
        //</editor-fold>
 
        /* Create and display the form */
        java.awt.EventQueue.invokeLater(new Runnable() {
            public void run() {
                new Euclidgui().setVisible(true);
            }
        });
    }
    // Variables declaration - do not modify                     
    private javax.swing.JButton ResetButton;
    private javax.swing.JLabel answerLabel;
    private javax.swing.JButton computeGcdButton;
    private javax.swing.JTextPane gcdTextAnswer;
    private javax.swing.JTextField input1Text;
    private javax.swing.JTextField input2Text;
    private javax.swing.JFormattedTextField jFormattedTextField1;
    private javax.swing.JInternalFrame jInternalFrame1;
    private javax.swing.JLabel jLabel1;
    private javax.swing.JLabel jLabel2;
    private javax.swing.JLabel jLabel3;
    private javax.swing.JScrollPane jScrollPane1;
    private javax.swing.JTextField jTextField1;
    private javax.swing.JButton lcmButton;
    // End of variables declaration                   
}

Ahh I guess I could adapt my code to work using subtraction although I'm not sure if that would make it less efficient. I'm pretty sure there's a way to get it to work with modulus but I can't wrap my head around the BigInteger class to get it working.

You can do it in BigInteger, you just have to tell it to do the same thing as your int method. I was wrong in my first post, a.compareTo(b) compares the wrong numbers and doesn't work because of it.

while (a.compareTo(BigInteger.ZERO) != 0 && b.compareTo(BigInteger.ZERO) != 0)

not

while(a.compareTo(b) != 0)

We need it to do the same thing in your bigIntger method, as it does in the int method, therefore, it has to run, comparing each value to zero instead of each other. The modulo works fine, so long as the looping statement is fine.