1 /*
   2  * Copyright (c) 2013 Oracle and/or its affiliates. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  *   - Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  *
  11  *   - Redistributions in binary form must reproduce the above copyright
  12  *     notice, this list of conditions and the following disclaimer in the
  13  *     documentation and/or other materials provided with the distribution.
  14  *
  15  *   - Neither the name of Oracle nor the names of its
  16  *     contributors may be used to endorse or promote products derived
  17  *     from this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  20  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31 
  32 /*
  33  * This source code is provided to illustrate the usage of a given feature
  34  * or technique and has been deliberately simplified. Additional steps
  35  * required for a production-quality application, such as security checks,
  36  * input validation and proper error handling, might not be present in
  37  * this sample code.
  38  */
  39 package stream.parallel;
  40 
  41 import java.math.BigInteger;
  42 import java.util.stream.IntStream;
  43 
  44 /**
  45  * This demo shows how to use the parallel calculation to calculate Fibonacci
  46  * sequence. This is a 2-dimensional system of linear difference equations that
  47  * describes the Fibonacci sequence.
  48  *
  49  * @author tyan
  50  */
  51 public class Fibonacci {
  52     /**
  53      * A base matrix that will be used to calculate Fibonacci sequence.
  54      */
  55     private final static BigInteger[][] BASE
  56             = new BigInteger[][]{
  57                 {BigInteger.ONE, BigInteger.ONE},
  58                 {BigInteger.ONE, BigInteger.ZERO}
  59               } ;
  60 
  61     /**
  62      * @param args argument to run program
  63      */
  64     public static void main(String[] args) {
  65         try {
  66             if (args.length != 1) {
  67                 throw new Exception("Only allow one argument");
  68             }
  69             int position = Integer.parseInt(args[0]);
  70             if (position < 0) {
  71                 throw new Exception("Postiion must be a positive integer");
  72             }
  73             System.out.printf("The %dth fibonacci number is %s\n" , position,
  74                     (position != 1 && position != 2) ?
  75                             power(BASE, position)[0][1].toString() : "1");
  76         } catch (Exception nfe) {
  77             usage();
  78         }
  79     }
  80 
  81     /**
  82      * Matrix binaries operation multiplication.
  83      * @param matrix1 matrix to be multiplied.
  84      * @param matrix2 matrix to multiply.
  85      * @return A new generated matrix which has same number of rows as matrix1
  86      * and same number of columns as matrix2.
  87      */
  88     private static BigInteger[][] times(BigInteger[][] matrix1,
  89             BigInteger[][] matrix2) {
  90         //Initialize all elements to zero
  91         assert(matrix1.length == matrix2[0].length);
  92         BigInteger[][] result = IntStream.range(0, matrix1.length).
  93                 mapToObj(i -> IntStream.range(0, matrix2[0].length).
  94                     mapToObj(v -> BigInteger.ZERO).toArray(BigInteger[]::new)).
  95                 toArray(BigInteger[][]::new);
  96 
  97         for(int row = 0; row < matrix1.length; row++) {
  98             for(int col =0; col < matrix2[row].length; col++) {
  99                 for(int col1 =0; col1 < matrix1[row].length; col1++) {
 100                     result[row][col] = result[row][col].
 101                             add(matrix1[row][col1].
 102                                     multiply(matrix2[col1][col]));
 103                 }
 104             }
 105         }
 106         return result;
 107     }
 108 
 109     /**
 110      * Power operation to matrix. Requirement for power operation is matrix must
 111      * have same number row and column.
 112      * @param matrix base
 113      * @param n      the exponent
 114      * @return the value of the first argument raised to the power of the second
 115      * argument.
 116      */
 117     private static BigInteger[][] power(BigInteger[][] matrix, int n) {
 118         return IntStream.range(0, n).
 119                 mapToObj(i -> matrix).
 120                 parallel().
 121                 reduce(Fibonacci::times).
 122                 get();
 123     }
 124 
 125     /**
 126      * Usage of this program
 127      */
 128     public static void usage() {
 129         System.out.println("Usage: java Fibonacci Position");
 130         System.out.println("Postiion must be a positive integer");
 131     }
 132 }