きったんの頭_ん中☆

フィボナッチ数を求める Java Applet

n 番目のフィボナッチ数を計算 (n <= 100000)

// <applet code="FibApp.class" width="300" height="300"></applet>

/**
 * フィボナッチ数を求める Java Applet
 * @see https://mind.kittttttan.info/java/fibapp
 */

import java.applet.Applet;
import javax.swing.JPanel;
import javax.swing.JButton;
import javax.swing.JLabel;
import javax.swing.JTextField;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;

import java.awt.Container;
import java.awt.BorderLayout;

import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;

import java.math.BigInteger;

public class FibApp extends Applet implements ActionListener {
  private final static int MAX = 100000;
  private Container contentPane;
  private JPanel panel1;
  private JPanel panel2;
  private JButton btn;
  private JTextArea ta;
  private JScrollPane sp;
  private JLabel labelt;
  private JTextField tf;

  /**
   * Initialize
   */
  public void init() {
    btn = new JButton("OK");
    btn.addActionListener(this);

    tf = new JTextField("777", 7);
    //tf.setToolTipText("Input Integer");

    labelt = new JLabel("Time[ms]");
    ta = new JTextArea(15, 20);
    ta.setLineWrap(true);
    sp = new JScrollPane(ta);

    panel1 = new JPanel();
    panel1.add(tf);
    panel1.add(btn);
    panel1.add(labelt);

    panel2 = new JPanel();
    panel2.add(sp);

    add(panel1, BorderLayout.CENTER);
    add(panel2, BorderLayout.SOUTH);
  }

  /**
   * Called when button pushed
   */
  public void actionPerformed(ActionEvent e) {
    try {
      long start = System.currentTimeMillis();
      String s = tf.getText();
      int n = Integer.parseInt(s);
      if (n > MAX) {
        ta.setText("too BIG");
        labelt.setText("?ms");
        return;
      }
      BigInteger p = getFibs(n);
      long stop = System.currentTimeMillis();
      String ps = p.toString();
      String t = String.valueOf(stop - start) + "ms";
      ta.setText(ps);
      labelt.setText(t);
    } catch (NumberFormatException err) {
      ta.setText("Input 1, 2, ...");
      labelt.setText("?ms");
    } catch (ArrayIndexOutOfBoundsException err) {
      ta.setText("Input 1, 2, ...");
      labelt.setText("?ms");
    }
  }

  /**
   * <pre>
   *  |a b|   |d e|   |ad+be bd+ce|
   *  |   | x |   | = |           |
   *  |b c|   |e f|   |bd+ce be+cf|
   * </pre>
   */
	public static BigInteger[] utm2mul(BigInteger[] a, BigInteger[] b) {
		BigInteger ad = a[0].multiply(b[0]);
		BigInteger be = a[1].multiply(b[1]);
		BigInteger bd = a[1].multiply(b[0]);
		BigInteger ce = a[2].multiply(b[1]);
		BigInteger bdce = bd.add(ce);
		BigInteger cf = a[2].multiply(b[2]);
    BigInteger[] m = {
      ad.add(be),
			bdce,
			be.add(cf)
    };
		return m;
	}

  /**
   * Get <var>n</var>th Fibonacci number
   * <pre>
   *    |1 1|^n   |fib(n+1) fib(n)  |
   *    |   |   = |                 |
   *    |1 0|     |fib(n)   fib(n-1)|
   * </pre>
   * @param n
   * @return
   */
  public static BigInteger getFibs(int n){
		if (n-- > 0) {
			if (n-- == 1) {return BigInteger.ONE;}
			BigInteger[] m0 = {BigInteger.ONE, BigInteger.ONE, BigInteger.ZERO};
			BigInteger[] m = {BigInteger.ONE, BigInteger.ONE, BigInteger.ZERO};
	        for (; n > 0; n >>>= 1, m0 = utm2mul(m0, m0)) {
	          if ((n & 1) == 1) {m = utm2mul(m, m0);}
	        }
			return m[0];
		}
		return BigInteger.ZERO;
  }
}