CPS 109 Lecture Notes - Lecture 12: Regular Number, Edward Fredkin, Priority Queue

42 views17 pages
Lect 12: Examples
BIG HAMMING
import java.math.BigInteger;
import java.util.*;
// For further examples See: http://rosettacode.org/wiki/Hamming_numbers#Java
/**
* Compute the {code n}:th Hamming number by generating Hamming numbers in a priority
queue.
* @author Ilkka Kokkarinen
*/
// Brute force solution
public boolean isHamming(int n){
while(n % 5 == 0){ n = n/5;}
while(n % 3 == 0){ n = n/3;}
while(n % 2 == 0){ n = n/2;}
return n == 1;
}
// Brute force solution continued
// this will take a lifetime to execute bc the gaps between the hamming numbers are
exponential
public int hamming(int n){
int curr = 1;
while(true){
if(isHamming(curr)){
if(--n == 0){ return curr; }
}
curr++;
}
}
public class BigHamming { // have to use BigInteger class bc hamming numbers grow too big
private static final BigInteger[] muls = {
BigInteger.valueOf(2), BigInteger.valueOf(3), BigInteger.valueOf(5)
};
/**
* Compute the {@code n}:th Hamming number, with quiet operation.
* @param n The index of the Hammin number to compute.
*/
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 17 pages and 3 million more documents.

Already have an account? Log in
public BigInteger computeHamming(int n) {
return computeHamming(n, false);
}
/**
* Compute the {@code n}:th Hamming number.
* @param n The index of the Hammin number to compute.
* @param verbose Whether the method should output the number and timing statistics.
* @return The {code n}:th Hamming number.
*/
public static BigInteger computeHamming(int n, boolean verbose) { //verbose <- canonical
boolean parameter that controls method should be silent or not
// time format: number of miliseconds that have elapsed since the beginning of the year
1970 (from UNIX OS)
long startTime = System.currentTimeMillis(); // time in millisecond precision, not raw time
// Java 7/8 has a new package called java.time which is much better than prior versions for
the actual time related data
// The elements of the search frontier
PriorityQueue<BigInteger> frontierQ = new PriorityQueue<BigInteger>(); // smallest
element
HashSet<BigInteger> frontierS = new HashSet<BigInteger>(); // existing data structure
int maxFrontierSize = 1;
// Initialize the frontier
frontierQ.offer(BigInteger.ONE);
frontierS.add(BigInteger.ONE);
// Invariant: we have generated all Hamming numbers up to the smallest
// element in the frontier.
while(true) {
if(frontierS.size() > maxFrontierSize) {
maxFrontierSize = frontierS.size();
}
// Pop out the next Hamming number from the frontier
BigInteger curr = frontierQ.poll();
frontierS.remove(curr);
//System.out.println(curr);
if(n-- == 0) {
if(verbose) {
System.out.println("Time: " + (System.currentTimeMillis() - startTime) + " ms"); //
calls the time method again
// difference betweeen current time and start time is the time elapsed
System.out.println("Frontier max size: " + maxFrontierSize);
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 17 pages and 3 million more documents.

Already have an account? Log in
System.out.println("Result: " + curr);
}
return curr;
}
// Generate the next three numbers to the search frontier
for(BigInteger e : muls) {
BigInteger newB = curr.multiply(e);
if(!frontierS.contains(newB)) {
frontierQ.offer(newB);
frontierS.add(newB);
}
}
}
}
}
ELEMENTARY CELLULAR
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import javax.swing.event.*;
import java.awt.image.*;
/**
* RULE 110
* starting from a random state, the system re-organizes in a way that can
* simulate all computers
*/
/**
* A Swing component to display one-dimensional cellular automata, with
* time flowing to the vertical direction.
* @author Ilkka Kokkarinen
*/
public class ElementaryCellular extends JPanel {
private static final int TOP = 35; // sets the top starting point in the screen
private boolean[][] state;
// All sorts of Swing components with different listeners.
private JSlider ruleSlider;
private JCheckBox fredkinBox;
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 17 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class