Re-implemented volume detection. Added fundamental frequency detection.

Continued re-branding to J.A.R.V.I.S. Built framework for Voice Activity
Detection algorithm. Created Microphone Analyzer class. Updated
microphone class.

8 files changed, 535 insertions, 83 deletions

diff --git a/CHANGELOG.markdown b/CHANGELOG.markdown
index 2be4e72..7f0c5b0 100644
--- a/CHANGELOG.markdown
+++ b/CHANGELOG.markdown
@@ -5,6 +5,12 @@ Changelog corresponds with a tagged and signed Git commit.  This marks the chang
 A tagged commit may or may not have a corresponding binary version available.
 Format:  Tag: `<Corresponding Tag>`
 
+* Version 1.10 (Tag v1.100)
+    * Added new Microphone Analyzer class.
+    * Added volume and frequency detection and frame work for (Voice Activity Detection) 
+    * Microphone API updated to make it more usable.
+    * API re-branded as J.A.R.V.I.S. (Just A Reliable Vocal Interpreter & Synthesiser)
+
 * Version 1.06 (Tag v1.016)
     * Added support for synthesiser for strings longer than 100 characters (Credits to @Skylion007)
     * Added support for synthesiser for multiple languages, accents, and voices. (Credits to @Skylion007)
diff --git a/CREDITS.markdown b/CREDITS.markdown
index e712672..899cf54 100644
--- a/CREDITS.markdown
+++ b/CREDITS.markdown
@@ -1,4 +1,4 @@
-#Java-Speech API Credits
+#J.A.R.V.I.S. Speech API (Java-Speech API) Credits
 
 ##Credits
 The following people/organizations have helped provide functionality for the API,
@@ -15,6 +15,8 @@ The following people/organizations have helped provide functionality for the API
         * Synthesiser
             * Allows for text to speech translation
     * Homepage: http://google.com
-
-I would like to thank the above so much for your work, this wrapper/API could not have been
+* Princeton University
+	* The implemented FFT algorithm is derived from one on the university's website.
+	* Homepage: http://www.princeton.edu
+We would like to thank the above so much for your work, this wrapper/API could not have been
 created without it.
\ No newline at end of file
diff --git a/README.markdown b/README.markdown
index 2be698c..93c33a6 100644
--- a/README.markdown
+++ b/README.markdown
@@ -1,8 +1,8 @@
 #J.A.R.V.I.S. (Java-Speech-API)
 
-J.A.R.V.I.S. Speech API: Just A Real Vocal Interpreter & Synthesizer. 
-This is a project for the Java Speech API. Interprets vocal inputs into text and synthesises MP3Data from text input.
-(Think Steven Hawkings) Even includes language auto-detection! 
+J.A.R.V.I.S. Speech API: Just A Reliable Vocal Interpreter & Synthesizer. 
+This is a project for the Java Speech API. The program interprets vocal inputs into text and synthesizes voices from text input.
+The program supports dozens of languages and even has the ability to auto-detect languages! 
 
 ## Description
 The J.A.R.V.I.S. Speech API is designed to be simple and efficient, using the speech engines created by Google  
diff --git a/src/com/darkprograms/speech/microphone/Microphone.java b/src/com/darkprograms/speech/microphone/Microphone.java
index e31534e..c674a3e 100644
--- a/src/com/darkprograms/speech/microphone/Microphone.java
+++ b/src/com/darkprograms/speech/microphone/Microphone.java
@@ -1,6 +1,7 @@
 package com.darkprograms.speech.microphone;
 
 import javax.sound.sampled.*;
+
 import java.io.File;
 
 /**
@@ -91,6 +92,22 @@ public class Microphone {
     public Microphone(AudioFileFormat.Type fileType) {
         setState(CaptureState.CLOSED);
         setFileType(fileType);
+        initTargetDataLine();
+    }
+
+    /**
+     * Initializes the target data line.
+     */
+    private void initTargetDataLine(){
+        DataLine.Info dataLineInfo = new DataLine.Info(TargetDataLine.class, getAudioFormat());
+        try {
+			setTargetDataLine((TargetDataLine) AudioSystem.getLine(dataLineInfo));
+		} catch (LineUnavailableException e) {
+			// TODO Auto-generated catch block
+			e.printStackTrace();
+			return;
+		}
+
     }
 
 
@@ -135,84 +152,13 @@ public class Microphone {
 
     }
 
-    /**
-     * Gets the volume of the microphone input
-     * Interval is 100ms so allow 100ms for this method to run in your code or specify smaller interval.
-     * @return The volume of the microphone input or -1 if data-line is not available
-     */
-    public int getAudioVolume(){
-    	return getAudioVolume(100);
-    }
-    
-    /**
-     * Gets the volume of the microphone input
-     * @param interval: The length of time you would like to calculate the volume over in milliseconds.
-     * @return The volume of the microphone input or -1 if data-line is not available. 
-     */    
-    public int getAudioVolume(int interval){
-    	return calculateAudioVolume(this.getNumOfBytes(interval/1000d));
-    }
-    
-    /**
-     * Gets the volume of microphone input
-     * @param numOfBytes The number of bytes you want for volume interpretation
-     * @return The volume over the specified number of bytes or -1 if data-line is unavailable.
-     */
-    private int calculateAudioVolume(int numOfBytes){
-    	if(getTargetDataLine()!=null){
-    		byte[] data = new byte[numOfBytes];
-    		this.getTargetDataLine().read(data, 0, numOfBytes);
-    		return calculateRMSLevel(data);
-    	}
-		else{
-			return -1;
-		}
-    }
-    
-    /**
-     * Calculates the volume of AudioData which may be buffered data from a data-line
-     * @param audioData The byte[] you want to determine the volume of
-     * @return the calculated volume of audioData
-     */
-	private int calculateRMSLevel(byte[] audioData){
-		long lSum = 0;
-		for(int i=0; i<audioData.length; i++)
-			lSum = lSum + audioData[i];
-
-		double dAvg = lSum / audioData.length;
-
-		double sumMeanSquare = 0d;
-		for(int j=0; j<audioData.length; j++)
-			sumMeanSquare = sumMeanSquare + Math.pow(audioData[j] - dAvg, 2d);
-
-		double averageMeanSquare = sumMeanSquare / audioData.length;
-		return (int)(Math.pow(averageMeanSquare,0.5d) + 0.5);
-	}
-	
-	/**
-	 * Returns the number of bytes over interval for useful when figuring out how long to record.
-	 * @param seconds The length in seconds
-	 * @return the number of bytes the microphone will save.
-	 */
-	public int getNumOfBytes(int seconds){
-		return getNumOfBytes((double)seconds);
-	}
-	
-	/**
-	 * Returns the number of bytes over interval for useful when figuring out how long to record.
-	 * @param seconds The length in seconds
-	 * @return the number of bytes the microphone will output over the specified time.
-	 */
-	public int getNumOfBytes(double seconds){
-		return (int)(seconds*getAudioFormat().getSampleRate()*getAudioFormat().getFrameSize()+.5);
-	}
 	
     /**
      * The audio format to save in
      *
      * @return Returns AudioFormat to be used later when capturing audio from microphone
      */
-    private AudioFormat getAudioFormat() {
+    public AudioFormat getAudioFormat() {
         float sampleRate = 8000.0F;
         //8000,11025,16000,22050,44100
         int sampleSizeInBits = 16;
@@ -227,6 +173,28 @@ public class Microphone {
     }
 
     /**
+     * Opens the microphone, starting the targetDataLine.
+     * If it's already open, it does nothing.
+     */
+    public void open(){
+        if(getTargetDataLine()==null){
+        	initTargetDataLine();
+        }
+    	if(!getTargetDataLine().isOpen() && getState()==CaptureState.CLOSED){
+        	try {
+                setState(CaptureState.PROCESSING_AUDIO);
+        		getTargetDataLine().open(getAudioFormat());
+            	getTargetDataLine().start();
+			} catch (LineUnavailableException e) {
+				// TODO Auto-generated catch block
+				e.printStackTrace();
+				return;
+			}
+        }
+
+    }
+
+    /**
      * Close the microphone capture, saving all processed audio to the specified file.<br>
      * If already closed, this does nothing
      */
@@ -235,6 +203,7 @@ public class Microphone {
         } else {
             getTargetDataLine().stop();
             getTargetDataLine().close();
+            setState(CaptureState.CLOSED);
         }
     }
 
@@ -248,13 +217,11 @@ public class Microphone {
          */
         public void run() {
             try {
-                setState(CaptureState.PROCESSING_AUDIO);
                 AudioFileFormat.Type fileType = getFileType();
                 File audioFile = getAudioFile();
-                getTargetDataLine().open(getAudioFormat());
-                getTargetDataLine().start();
+                open();
                 AudioSystem.write(new AudioInputStream(getTargetDataLine()), fileType, audioFile);
-                setState(CaptureState.CLOSED);
+                //Will write to File until it's closed.
             } catch (Exception ex) {
                 ex.printStackTrace();
             }
diff --git a/src/com/darkprograms/speech/microphone/MicrophoneAnalyzer.java b/src/com/darkprograms/speech/microphone/MicrophoneAnalyzer.java
new file mode 100644
index 0000000..a9130b8
--- /dev/null
+++ b/src/com/darkprograms/speech/microphone/MicrophoneAnalyzer.java
@@ -0,0 +1,223 @@
+package com.darkprograms.speech.microphone;

+

+import javax.sound.sampled.AudioFileFormat;

+import com.darkprograms.speech.utility.*;

+

+/**

+ * Microphone Analyzer class, detects pitch and volume while extending the microphone class.

+ * Implemented as a precursor to a Voice Activity Detection (VAD) algorithm.

+ * Currently can be used for audio data analysis.

+ * Dependencies: FFT.java & Complex.java. Both found in the utility package.

+ */

+

+public class MicrophoneAnalyzer extends Microphone {

+

+	/**

+	 * Constructor

+	 * @param fileType The file type you want to save in. FLAC recommended.

+	 */

+	public MicrophoneAnalyzer(AudioFileFormat.Type fileType){

+		super(fileType);

+	}

+	

+    /**

+     * Gets the volume of the microphone input

+     * Interval is 100ms so allow 100ms for this method to run in your code or specify smaller interval.

+     * @return The volume of the microphone input or -1 if data-line is not available

+     */

+    public int getAudioVolume(){

+    	return getAudioVolume(100);

+    }

+    

+    /**

+     * Gets the volume of the microphone input

+     * @param interval: The length of time you would like to calculate the volume over in milliseconds.

+     * @return The volume of the microphone input or -1 if data-line is not available. 

+     */    

+    public int getAudioVolume(int interval){

+    	return calculateAudioVolume(this.getNumOfBytes(interval/1000d));

+    }

+    

+    /**

+     * Gets the volume of microphone input

+     * @param numOfBytes The number of bytes you want for volume interpretation

+     * @return The volume over the specified number of bytes or -1 if data-line is unavailable.

+     */

+    private int calculateAudioVolume(int numOfBytes){

+    	byte[] data = getBytes(numOfBytes);

+    	if(data==null)

+    		return -1;

+    	return calculateRMSLevel(data);

+    }

+    

+    /**

+     * Calculates the volume of AudioData which may be buffered data from a data-line.

+     * @param audioData The byte[] you want to determine the volume of

+     * @return the calculated volume of audioData

+     */

+	public static int calculateRMSLevel(byte[] audioData){

+		long lSum = 0;

+		for(int i=0; i<audioData.length; i++)

+			lSum = lSum + audioData[i];

+

+		double dAvg = lSum / audioData.length;

+

+		double sumMeanSquare = 0d;

+		for(int j=0; j<audioData.length; j++)

+			sumMeanSquare = sumMeanSquare + Math.pow(audioData[j] - dAvg, 2d);

+

+		double averageMeanSquare = sumMeanSquare / audioData.length;

+		return (int)(Math.pow(averageMeanSquare,0.5d) + 0.5);

+	}

+	

+	/**

+	 * Returns the number of bytes over interval for useful when figuring out how long to record.

+	 * @param seconds The length in seconds

+	 * @return the number of bytes the microphone will save.

+	 */

+	public int getNumOfBytes(int seconds){

+		return getNumOfBytes((double)seconds);

+	}

+	

+	/**

+	 * Returns the number of bytes over interval for useful when figuring out how long to record.

+	 * @param seconds The length in seconds

+	 * @return the number of bytes the microphone will output over the specified time.

+	 */

+	public int getNumOfBytes(double seconds){

+		return (int)(seconds*getAudioFormat().getSampleRate()*getAudioFormat().getFrameSize()+.5);

+	}

+	

+	/**

+	 * Returns the a byte[] containing the specified number of bytes

+	 * @param numOfBytes The length of the returned array.

+	 * @return The specified array or null if it cannot.

+	 */

+	private byte[] getBytes(int numOfBytes){

+		if(getTargetDataLine()!=null){

+    		byte[] data = new byte[numOfBytes];

+    		this.getTargetDataLine().read(data, 0, numOfBytes);

+    		return data;

+		}

+		return null;//If data cannot be read, returns a null array.

+	}

+	

+

+	/**

+	 * Calculates the fundamental frequency. In other words, it calculates pitch,

+	 * except pitch is far more subjective and subtle. Also note, that readings may occasionally,

+	 * be in error due to the complex nature of sound. This feature is in Beta

+	 * @return The frequency of the sound in Hertz.

+	 */

+	public int getFrequency(){

+		try {

+			return getFrequency(1024);

+		} catch (Exception e) {

+			//This will never happen. Ever...

+			return -666;

+		}

+	}

+

+	/**

+	 * Calculates the frequency based off of the number of bytes. 

+	 * CAVEAT: THE NUMBER OF BYTES MUST BE A MULTIPLE OF 2!!!

+	 * @param numOfBytes The number of bytes which must be a multiple of 2!!!

+	 * @return The calculated frequency in Hertz.

+	 */

+	public int getFrequency(int numOfBytes) throws Exception{

+		if(getTargetDataLine() == null){

+			return -1;

+		}

+		byte[] data = new byte[numOfBytes+1];//One byte is lost during conversion

+    	this.getTargetDataLine().read(data, 0, numOfBytes);

+		return getFrequency(data);

+	}

+	

+	/**

+	 * Calculates the frequency based off of the byte array,

+	 * @param bytes The audioData you want to analyze

+	 * @return The calculated frequency in Hertz.

+	 */

+	private int getFrequency(byte[] bytes){//This method requires an AudioFormat and cannot be static.

+		double[] audioData = this.bytesToDoubleArray(bytes);

+		Complex[] complex = new Complex[audioData.length];

+		for(int i = 0; i<complex.length; i++){

+			complex[i] = new Complex(audioData[i], 0);

+		}

+		Complex[] fftTransformed = FFT.fft(complex);

+		return calculateFundamentalFrequency(fftTransformed);

+	}

+	

+	/**

+	 * Iterates through the transformed data to calculate the frequency

+	 * This data is only as accurate as the bin size. (See getBinSize(int))

+	 * Fundamental Frequency = index of max magnitude (that isn't a harmotic) * bin size

+	 * @param fftData The data you want to analyze

+	 * @return The frequency in Hertz

+	 */

+	private int calculateFundamentalFrequency(Complex[] fftData){

+		int index = -1;

+		double max = Double.MIN_VALUE;

+		for(int i = 0; i<fftData.length/2; i++){

+			Complex complex = fftData[i];

+			double tmp = complex.getMagnitude();

+			if(tmp>max && !isHarmonic(i,index)){

+				max = tmp;

+				index = i;

+			}

+		}

+		return index*getFFTBinSize(fftData.length);

+	}

+	

+	/**

+	 * Determines whether or not a specific index constitutes a harmonic of a previous instance.

+	 * Science: A harmonic frequency is a multiple of the fundamental frequency caused by interference.

+	 * Note: Frequencies of an index 1 won't be treated as such since its frequency is so low.

+	 * @param currentIndex The suspected harmonic frequency

+	 * @param proposedIndex The suspected fundamental frequency

+	 * @return True if it is a haromonic, false if it's not.

+	 */

+	private boolean isHarmonic(int currentIndex, int proposedIndex){

+		return (currentIndex>2 && proposedIndex>2 && currentIndex%proposedIndex==0);

+	}

+	

+	/**

+	 * Calculates the FFTbin size based off the length of the the array

+	 * Each FFTBin size represents the range of frequencies treated as one.

+	 * For example, if the bin size is 5 then the algorithm is precise to within 5hz.

+	 * Precondition: length cannot be 0.

+	 * @param fftDataLength The length of the array used to feed the FFT algorithm

+	 * @return FFTBin size

+	 */

+	private int getFFTBinSize(int fftDataLength){

+		return (int)(getAudioFormat().getSampleRate()/fftDataLength+.5);

+	}

+	

+	/**

+	 * Converts bytes from a TargetDataLine into a double[] allowing the information to be read.

+	 * NOTE: One byte is lost in the conversion so don't expect the arrays to be the same length!

+	 * @param bufferData The buffer read in from the target data line

+	 * @return The double[] that the buffer has been converted into.

+	 */

+	private double[] bytesToDoubleArray(byte[] bufferData){

+	    final int bytesRecorded = bufferData.length;

+		final int bytesPerSample = getAudioFormat().getSampleSizeInBits()/8; 

+	    final double amplification = 100.0; // choose a number as you like

+	    double[] micBufferData = new double[bytesRecorded - bytesPerSample +1];

+	    for (int index = 0, floatIndex = 0; index < bytesRecorded - bytesPerSample + 1; index += bytesPerSample, floatIndex++) {

+	        double sample = 0;

+	        for (int b = 0; b < bytesPerSample; b++) {

+	            int v = bufferData[index + b];

+	            if (b < bytesPerSample - 1 || bytesPerSample == 1) {

+	                v &= 0xFF;

+	            }

+	            sample += v << (b * 8);

+	        }

+	        double sample32 = amplification * (sample / 32768.0);

+	        micBufferData[floatIndex] = sample32;

+	        

+	    }

+	    return micBufferData;

+	}

+	

+}

diff --git a/src/com/darkprograms/speech/recognizer/Recognizer.java b/src/com/darkprograms/speech/recognizer/Recognizer.java
index 5efa491..6c24d3b 100644
--- a/src/com/darkprograms/speech/recognizer/Recognizer.java
+++ b/src/com/darkprograms/speech/recognizer/Recognizer.java
@@ -179,6 +179,7 @@ public class Recognizer {
     
     /**Language code.  This language code must match the language of the speech to be recognized. ex. en-US ru-RU
      * This value is null by default.
+     * @param language The language code.
      */
      @Deprecated
     public void setLanguage(String language) {
@@ -197,7 +198,7 @@ public class Recognizer {
     /**
      * Language code.  This language code must match the language of the speech to be recognized. ex. en-US ru-RU
      * This value is null by default.
-     * @return language
+     * @return language the Google language
      */
     public String getLanguage(){
     	return language;
diff --git a/src/com/darkprograms/speech/utility/Complex.java b/src/com/darkprograms/speech/utility/Complex.java
new file mode 100644
index 0000000..814bebb
--- /dev/null
+++ b/src/com/darkprograms/speech/utility/Complex.java
@@ -0,0 +1,120 @@
+package com.darkprograms.speech.utility;

+

+

+/*************************************************************************

+ *  Compilation:  javac Complex.java

+ *  Execution:    java Complex

+ *

+ *  Data type for complex numbers.

+ *

+ *  The data type is "immutable" so once you create and initialize

+ *  a Complex object, you cannot change it. The "final" keyword

+ *  when declaring re and im enforces this rule, making it a

+ *  compile-time error to change the .re or .im fields after

+ *  they've been initialized.

+ *

+ *  Class based off of Princeton University's Complex.java class

+ *  @author Aaron Gokaslan, Princeton University

+ *************************************************************************/

+

+public class Complex {

+    private final double re;   // the real part

+    private final double im;   // the imaginary part

+

+    // create a new object with the given real and imaginary parts

+    public Complex(double real, double imag) {

+        re = real;

+        im = imag;

+    }

+

+    // return a string representation of the invoking Complex object

+    public String toString() {

+        if (im == 0) return re + "";

+        if (re == 0) return im + "i";

+        if (im <  0) return re + " - " + (-im) + "i";

+        return re + " + " + im + "i";

+    }

+

+    // return abs/modulus/magnitude and angle/phase/argument

+    public double abs()   { return Math.hypot(re, im); }  // Math.sqrt(re*re + im*im)

+    public double phase() { return Math.atan2(im, re); }  // between -pi and pi

+

+    // return a new Complex object whose value is (this + b)

+    public Complex plus(Complex b) {

+        Complex a = this;             // invoking object

+        double real = a.re + b.re;

+        double imag = a.im + b.im;

+        return new Complex(real, imag);

+    }

+

+    // return a new Complex object whose value is (this - b)

+    public Complex minus(Complex b) {

+        Complex a = this;

+        double real = a.re - b.re;

+        double imag = a.im - b.im;

+        return new Complex(real, imag);

+    }

+

+    // return a new Complex object whose value is (this * b)

+    public Complex times(Complex b) {

+        Complex a = this;

+        double real = a.re * b.re - a.im * b.im;

+        double imag = a.re * b.im + a.im * b.re;

+        return new Complex(real, imag);

+    }

+

+    // scalar multiplication

+    // return a new object whose value is (this * alpha)

+    public Complex times(double alpha) {

+        return new Complex(alpha * re, alpha * im);

+    }

+

+    // return a new Complex object whose value is the conjugate of this

+    public Complex conjugate() {  return new Complex(re, -im); }

+

+    // return a new Complex object whose value is the reciprocal of this

+    public Complex reciprocal() {

+        double scale = re*re + im*im;

+        return new Complex(re / scale, -im / scale);

+    }

+

+    // return the real or imaginary part

+    public double re() { return re; }

+    public double im() { return im; }

+

+    // return a / b

+    public Complex divides(Complex b) {

+        Complex a = this;

+        return a.times(b.reciprocal());

+    }

+

+    // return a new Complex object whose value is the complex exponential of this

+    public Complex exp() {

+        return new Complex(Math.exp(re) * Math.cos(im), Math.exp(re) * Math.sin(im));

+    }

+

+    // return a new Complex object whose value is the complex sine of this

+    public Complex sin() {

+        return new Complex(Math.sin(re) * Math.cosh(im), Math.cos(re) * Math.sinh(im));

+    }

+

+    // return a new Complex object whose value is the complex cosine of this

+    public Complex cos() {

+        return new Complex(Math.cos(re) * Math.cosh(im), -Math.sin(re) * Math.sinh(im));

+    }

+

+    // return a new Complex object whose value is the complex tangent of this

+    public Complex tan() {

+        return sin().divides(cos());

+    }

+

+    // returns the magnitude of the imaginary number.

+    public double getMagnitude(){

+    	return Math.sqrt(re*re+im*im);

+    }

+    

+    public boolean equals(Complex other){

+    	return (re==other.re) && (im==other.im);

+    }

+    

+}

diff --git a/src/com/darkprograms/speech/utility/FFT.java b/src/com/darkprograms/speech/utility/FFT.java
new file mode 100644
index 0000000..a131896
--- /dev/null
+++ b/src/com/darkprograms/speech/utility/FFT.java
@@ -0,0 +1,133 @@
+package com.darkprograms.speech.utility;

+

+

+/*************************************************************************

+ *  Compilation:  javac FFT.java

+ *  Execution:    java FFT N

+ *  Dependencies: Complex.java

+ *

+ *  Compute the FFT and inverse FFT of a length N complex sequence.

+ *  Bare bones implementation that runs in O(N log N) time. Our goal

+ *  is to optimize the clarity of the code, rather than performance.

+ *

+ *  Limitations

+ *  -----------

+ *   -  assumes N is a power of 2

+ *

+ *   -  not the most memory efficient algorithm (because it uses

+ *      an object type for representing complex numbers and because

+ *      it re-allocates memory for the subarray, instead of doing

+ *      in-place or reusing a single temporary array)

+ *  

+ *************************************************************************/

+

+/*************************************************************************

+ * @author Skylion implementation 

+ * @author Princeton University for the actual algorithm.

+ ************************************************************************/

+

+public class FFT {

+

+    // compute the FFT of x[], assuming its length is a power of 2

+    public static Complex[] fft(Complex[] x) {

+        int N = x.length;

+

+        // base case

+        if (N == 1) return new Complex[] { x[0] };

+

+        // radix 2 Cooley-Tukey FFT

+        if (N % 2 != 0) { throw new RuntimeException("N is not a power of 2"); }

+

+        // fft of even terms

+        Complex[] even = new Complex[N/2];

+        for (int k = 0; k < N/2; k++) {

+            even[k] = x[2*k];

+        }

+        Complex[] q = fft(even);

+

+        // fft of odd terms

+        Complex[] odd  = even;  // reuse the array

+        for (int k = 0; k < N/2; k++) {

+            odd[k] = x[2*k + 1];

+        }

+        Complex[] r = fft(odd);

+

+        // combine

+        Complex[] y = new Complex[N];

+        for (int k = 0; k < N/2; k++) {

+            double kth = -2 * k * Math.PI / N;

+            Complex wk = new Complex(Math.cos(kth), Math.sin(kth));

+            y[k]       = q[k].plus(wk.times(r[k]));

+            y[k + N/2] = q[k].minus(wk.times(r[k]));

+        }

+        return y;

+    }

+

+

+    // compute the inverse FFT of x[], assuming its length is a power of 2

+    public static Complex[] ifft(Complex[] x) {

+        int N = x.length;

+        Complex[] y = new Complex[N];

+

+        // take conjugate

+        for (int i = 0; i < N; i++) {

+            y[i] = x[i].conjugate();

+        }

+

+        // compute forward FFT

+        y = fft(y);

+

+        // take conjugate again

+        for (int i = 0; i < N; i++) {

+            y[i] = y[i].conjugate();

+        }

+

+        // divide by N

+        for (int i = 0; i < N; i++) {

+            y[i] = y[i].times(1.0 / N);

+        }

+

+        return y;

+

+    }

+

+    // compute the circular convolution of x and y

+    public static Complex[] cconvolve(Complex[] x, Complex[] y) {

+

+        // should probably pad x and y with 0s so that they have same length

+        // and are powers of 2

+        if (x.length != y.length) { throw new RuntimeException("Dimensions don't agree"); }

+

+        int N = x.length;

+

+        // compute FFT of each sequence

+        Complex[] a = fft(x);

+        Complex[] b = fft(y);

+

+        // point-wise multiply

+        Complex[] c = new Complex[N];

+        for (int i = 0; i < N; i++) {

+            c[i] = a[i].times(b[i]);

+        }

+

+        // compute inverse FFT

+        return ifft(c);

+    }

+

+

+    // compute the linear convolution of x and y

+    public static Complex[] convolve(Complex[] x, Complex[] y) {

+        Complex ZERO = new Complex(0, 0);

+

+        Complex[] a = new Complex[2*x.length];

+        for (int i = 0;        i <   x.length; i++) a[i] = x[i];

+        for (int i = x.length; i < 2*x.length; i++) a[i] = ZERO;

+

+        Complex[] b = new Complex[2*y.length];

+        for (int i = 0;        i <   y.length; i++) b[i] = y[i];

+        for (int i = y.length; i < 2*y.length; i++) b[i] = ZERO;

+

+        return cconvolve(a, b);

+    }

+

+}