Skip to content

Instantly share code, notes, and snippets.

@Minecraftian14

Minecraftian14/FibbMod.java

Last active August 6, 2025 04:04
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Minecraftian14/6cd7db5dd94585935a55d49ca48af6c8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Minecraftian14/6cd7db5dd94585935a55d49ca48af6c8 to your computer and use it in GitHub Desktop.
Download ZIP
Fibonacci Modulo
Raw
FibbMod.java
// java -Xss1g -Xmx12g FibbMod.java & exit
package in.mcxiv.fibbmods;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.regex.Pattern;
import java.util.stream.IntStream;
public class FibbMod {
public static long dtl(double n) {
if (n > Long.MAX_VALUE) throw new UnsupportedOperationException("Input reached 2^63-1");
return (long) n;
}
/**
* Simple Recursion
*/
public static int fibbmod1(long n, long m) {
return (int) (n < 2 ? n : (fibbmod1(n - 1, m) + fibbmod1(n - 2, m)) % m);
}
/**
* Memoized Recursion
*/
public static int fibbmod2(long n, long m) {
return fibbmod2step(n, m, new HashMap<>(Map.of(0L, 0, 1L, 1)));
}
private static int fibbmod2step(long n, long m, HashMap<Long, Integer> map) {
if (map.containsKey(n)) return map.get(n);
var ans = (int) ((fibbmod2step(n - 1, m, map) + fibbmod2step(n - 2, m, map)) % m);
map.put(n, ans);
return ans;
}
/**
* Simple Looping
*/
public static int fibbmod3(long n, long m) {
if (n < 2) return (int) n;
long ans = 2L, a = 0L, b = 1L;
for (var i = 2; i <= n; i++) {
ans = (a + b) % m;
a = b;
b = ans;
}
return (int) ans;
}
public static int fibbmod3unsigned(long n, int m) {
if (n >= 0 && n <= 1) return (int) n;
int a = 0, b = 1;
n = n < 0 ? Long.remainderUnsigned(n, 6L * m) : n % (6L * m);
do {
int ans = a + b;
if (ans >= m) ans -= m;
a = b;
b = ans;
} while (--n > 0);
return a;
}
/**
* Simple Dictionary
*/
public static int fibbmod4(long n, long m) {
HashMap<Long, Integer> map = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>(List.of(0, 1));
long a = 0, b = 1;
do {
int ans = (int) ((a + b) % m);
map.put(a * m + b, ans);
list.add(ans);
a = b;
b = ans;
} while (!map.containsKey(a * m + b));
// prt(map.size());
return list.get((int) (n % map.size()));
}
public static BigInteger dtbi(double n) {
return BigDecimal.valueOf(n).toBigInteger();
}
public static BigInteger dtbix(double n) {
if (n > 999999999) throw new UnsupportedOperationException("Input reached 2^999999999");
return BigDecimal.TWO.pow((int) n).toBigInteger();
}
/**
* BigInteger Dictionary
*/
public static int fibbmod5(BigInteger n, long m) {
HashMap<Long, Integer> map = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>(List.of(0, 1));
long a = 0, b = 1;
do {
int ans = (int) ((a + b) % m);
map.put(a * m + b, ans);
list.add(ans);
a = b;
b = ans;
} while (!map.containsKey(a * 100 + b));
// long
return list.get(n.mod(BigInteger.valueOf(map.size())).intValue());
}
/**
* Base2^32, Dictionary
*/
public static class LargeNumber {
private final long base;
private final int[] digits; // digits[0] is MSD
public LargeNumber(int[] digits) {
this.base = 1L << 32;
this.digits = digits.clone();
}
public LargeNumber(Scanner sc) {
this.base = 1_000_000_000;
var digits = new ArrayList<Integer>();
int bickeringOffset = 0;
while (sc.hasNext()) {
String line = sc.nextLine().trim();
if (!line.matches("\\d+")) break;
for (int i = 0; i < line.length(); i += 9) {
var word = line.substring(i, Math.min(line.length(), i + 9));
int digit = Integer.parseInt(word);
if (bickeringOffset == 0) {
// If input is 2345, we save 234500000
bickeringOffset = 9 - word.length();
digits.add(digit * (int) Math.pow(10, bickeringOffset));
} else {
// If input is 23456789 and bo is 5, we modify last to xxxx23456 and add 789000000
int value = (int) Math.log10(digit) + 1;
int exist = (int) (digit * Math.pow(10, bickeringOffset - value));
int anewd = digit % (int) Math.pow(10, value - bickeringOffset);
bickeringOffset = (9 - bickeringOffset + value) % 5;
digits.set(digits.size() - 1, digits.getLast() + exist);
if (anewd > 0) digits.add(anewd * (int) Math.pow(10, bickeringOffset));
}
}
}
if (bickeringOffset > 0) {
// bo=4, [123456789, 123456789, 98765] -> [12345, 678912345, 678998765]
int carry = 0;
int bot = (int) Math.pow(10, bickeringOffset);
int bit = (int) Math.pow(10, 9 - bickeringOffset);
for (int i = 0, s = digits.size(); i < s; i++) {
int digit = digits.get(i);
int shift = digit % bot;
digit = carry * bit + digit / bot;
carry = shift;
digits.set(i, digit);
}
}
this.digits = digits.stream().mapToInt(Integer::valueOf).toArray();
}
public LargeNumber(String s) {
this(new Scanner(s));
}
public int mod(int m) {
int result = 0;
// To support negative numbers
// long dirt = 2L * Integer.MAX_VALUE - 2;
// a=-18 -> (dirt+a)%m === Integer.toUnsignedLong(digit)%m
for (int digit : digits)
result = (int) ((result * base + Integer.toUnsignedLong(digit)) % m);
return result;
}
@Override
public String toString() {
return "(" + Arrays.toString(digits) + ")b." + base;
}
}
public static int[] dtia(double n) {
var nn = BigDecimal.valueOf(n).toBigInteger();
var mn = BigInteger.valueOf(1L << 32);
var digits = new ArrayList<Integer>();
while (nn.compareTo(BigInteger.ZERO) > 0) {
digits.add(nn.remainder(mn).intValue());
nn = nn.divide(mn);
}
Collections.reverse(digits);
return digits.stream().mapToInt(Integer::valueOf).toArray();
}
public static int[] dtiax(double n) {
if (n > Integer.MAX_VALUE) throw new UnsupportedOperationException("Input reached 2^32^(2^31-1)");
int[] digits = new int[(int) n];
digits[0] = 1;
return digits;
}
public static LargeNumber dtln(double n) {
if (n > Double.MAX_VALUE) throw new UnsupportedOperationException("Input reached 1.79E+308");
return new LargeNumber(dtia(n));
}
public static LargeNumber dtlnx(double n) {
if (n > Integer.MAX_VALUE) throw new UnsupportedOperationException("Input reached 10^9^(2^31-1)");
long digits = 1 + (long) n * 9L;
long[] iterations = {0};
int[] restCounter = {9 * 16};
return new LargeNumber(new Scanner(new InputStreamReader(new InputStream() {
@Override
public int read() {
if (restCounter[0] == 0) {
restCounter[0] = 9 * 16;
return '\n';
}
restCounter[0]--;
if (iterations[0] >= digits) return -1;
return iterations[0]++ == 0 ? '1' : '0';
}
})));
}
public static int fibbmod6(int[] digits, int m) {
HashMap<Long, Integer> map = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>(List.of(0, 1));
long a = 0, b = 1;
do {
int ans = (int) ((a + b) % m);
map.put(a * m + b, ans);
list.add(ans);
a = b;
b = ans;
} while (!map.containsKey(a * m + b));
var n = new LargeNumber(digits);
return list.get(n.mod(map.size()));
}
/**
* Better Modulo
*/
public static int fibbmod7(int[] digits, int m) {
var list = new ArrayList<>(List.of(0, 1));
int a = 0, b = 1;
do {
int ans = a + b;
if (ans >= m) ans -= m;
list.add(ans);
a = b;
b = ans;
} while (!(a == 0 && b == 1));
list.removeLast();
list.removeLast();
var n = new LargeNumber(digits);
return list.get(n.mod(list.size()));
}
/**
* Base2^32, any k offset
*/
public static int fibbmod8(int[] digits, int m, int k) {
if (digits.length == 1 && digits[0] < k) return digits[0];
// %0 is nothing, %1 is useless. [0] is nothing.
assert m > 1 && k >= 1;
// No repetition
assert k % m > 0;
// Minimum viable number
assert digits.length >= 1;
List<Integer> list = new ArrayList<>(k);
// VERY IMPORTANT: According to the question, f(i) = i for every i < 100
// for (int i = 0; i < k; i++) list.add(i % m);
for (int i = 0; i < k; i++) list.add(i);
// Just assurance of the repetition property
assert list.get(0) == 0;
assert list.get(1) == 1;
int a = k - 1, b = 0; // b = k - k
do {
list.add((list.get(a) + list.get(b)) % m);
a++;
b++;
} while (!(list.get(a) == 0 && list.get(b) == 1));
// Remove the [0..99] part, which is not needed
for (int i = 0; i < k; i++)
list.set(i, list.get(i) % m);
// Remove reseeds of 0 and 1
list.removeLast();
var n = new LargeNumber(digits);
return list.get(n.mod(list.size()));
}
public static class Matrix22 {
int a00, a01;
int a10, a11;
public Matrix22(int a00, int a01, int a10, int a11) {
this.a00 = a00;
this.a01 = a01;
this.a10 = a10;
this.a11 = a11;
}
public void set(int b00, int b01, int b10, int b11) {
a00 = b00;
a01 = b01;
a10 = b10;
a11 = b11;
}
public void cross(Matrix22 b, int m) {
set(
(a00 * b.a00 + a01 * b.a10) % m,
(a00 * b.a01 + a01 * b.a11) % m,
(a10 * b.a00 + a11 * b.a10) % m,
(a10 * b.a01 + a11 * b.a11) % m
);
}
public Matrix22 exponentiate(long n, int m) {
if (n < 0) throw new UnsupportedOperationException("Not yet thought of implementing");
if (n == 0) throw new UnsupportedOperationException("Identity?");
if (n == 1) return this;
var buf = new Matrix22(a00, a01, a10, a11);
set(1, 0, 0, 1);
while (n > 0) {
if ((n & 1) == 0) {
buf.cross(buf, m);
n >>>= 1;
} else {
cross(buf, m);
n -= 1;
}
}
return this;
}
public Matrix22 set(Matrix22 c) {
set(c.a00, c.a01, c.a10, c.a11);
return this;
}
@Override
public String toString() {
return "[[" + a00 + ", " + a01 + "][" + a10 + ", " + a11 + "]]";
}
}
/**
* Fast Matrix Exponentiation
*/
public static int fibbmod9(long n, int m) {
if (n <= 1) return (int) n;
return new Matrix22(1, 1, 1, 0).exponentiate(n - 1, m).a00;
}
public static class Matrix {
long[] data;
long[] buffer;
int rows, cols;
public Matrix(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.data = new long[rows * cols];
this.buffer = new long[rows * cols];
}
public Matrix(int rows, int cols, long[] data) {
assert data.length >= rows * cols;
this.rows = rows;
this.cols = cols;
this.data = data.clone();
this.buffer = new long[rows * cols];
}
public int idx(int r, int c) {
return r * cols + c;
}
public void set(int r, int c, long v) {
data[idx(r, c)] = v;
}
public Matrix set(Matrix m) {
System.arraycopy(m.data, 0, data, 0, data.length);
return this;
}
public long get(int r, int c) {
return data[idx(r, c)];
}
public Matrix initIdentity() {
Arrays.fill(data, 0);
for (int i = 0, s = Math.min(rows, cols); i < s; i++)
set(i, i, 1);
return this;
}
public void square(long m) {
int s = Math.min(rows, cols);
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
long v = 0;
for (int j = 0; j < s; j++)
v += get(r, j) * get(j, c);
buffer[idx(r, c)] = v % m;
}
}
System.arraycopy(buffer, 0, data, 0, data.length);
}
public void cross(Matrix o, long m) {
assert cols == o.rows;
if (buffer.length < rows * o.cols)
buffer = new long[rows * o.cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < o.cols; c++) {
long v = 0;
for (int i = 0; i < cols; i++) v += get(r, i) * o.get(i, c);
buffer[idx(r, c)] = v % m;
}
}
System.arraycopy(buffer, 0, data, 0, data.length);
}
public Matrix exponentiate(long n, long m) {
if (n < 0) throw new UnsupportedOperationException("Not yet thought of implementing");
if (n == 0) throw new UnsupportedOperationException("Identity?");
if (n == 1) return this;
var buf = new Matrix(rows, cols, data);
initIdentity();
while (n > 0) {
if ((n & 1) == 0) {
buf.square(m);
n >>>= 1;
} else {
cross(buf, m);
n -= 1;
}
}
return this;
}
}
/**
* Fast Matrix Exponentiation, any a, b offset
*/
public static long fibbmod10(long n, long m, int a, int b) {
assert a > 0 && b > 0;
int s = Math.max(a, b);
if (n < s) return (int) n;
// Assuming, that F[i] = i for every i < b
// |Fn | = |0 . 1 . 1| * |Fn-1| = A^n-1 * |F(b-1)| = A^n-1 * |b-1|
// |Fn-1 | |1 0 ... 0| |Fn-2| |F(b-2)| |b-2|
// |Fn-2 | |0 1 ... 0| |Fn-3| |F(b-3)| |b-3|
// ...... ......... .... ...... ...
// |Fn-a+1| |0 . 1 . 0| |Fn-a| |F(b-a)| |b-a|
// ...... ......... .... ...... ...
// |Fn-b+1| |0 ... 1 0| |Fn-b| |F(0) | |0 |
//
// Fn = summation [i=0..b-1] { A^n-1[0, i] * (b-1-i) }
var ma = new Matrix(s, s);
ma.set(0, a - 1, 1);
ma.set(0, b - 1, 1);
for (int i = 1; i < s; i++) ma.set(i, i - 1, 1);
ma.exponentiate(n - 1, m);
long answer = 0;
for (int i = 0; i <= b - 1; i++)
answer = (answer + ma.get(0, i) * (b - 1 - i)) % m;
return answer;
}
public static String dts(double d) {
return dtbi(d).toString();
}
public static String dtsx(double d) {
return dtbix(d).toString();
}
/**
* FME, Str input
*/
public static int fibbmod11(String n, int m) {
if (Objects.equals(n, "0")) return 0;
if (Objects.equals(n, "1")) return 1;
if (Objects.equals(n, "2")) return 1;
var ma = new Matrix22(1, 1, 1, 0);
var mc = new Matrix22(1, 0, 0, 1);
var mt = new Matrix22(0, 0, 0, 0);
// For N = 123, A^N = A^123
// = A^( 1 * 100 + 2 * 10 + 3 * 1 )
// = A^( ( ( 1 * 10 ) + 2 ) * 10 + 3 )
// Therefore, as we gain digits of N, we can proceed as:
// C := A ^ d1
// C := C ^ 10 * A ^ d2
// C := C ^ 10 * A ^ d3
// And hence, we have C = A^N
// This can not be solved using the previous method, since we do not have F(-1)
// |Fn | = |0 . 1 . 1| * |Fn-1 | = A^n-1 * |F(b-1)| = A^n * |F(b-2) | = A^n * |b-2 |
// |Fn-1 | |1 0 ... 0| |Fn-2 | |F(b-2)| |F(b-3) | |b-3 |
// |Fn-2 | |0 1 ... 0| |Fn-3 | |F(b-3)| |F(b-4) | |b-4 |
// ...... ......... .... ...... ........ .....
// |Fn-a+1| |0 . 1 . 0| |Fn-a | |F(b-a)| |F(b-a-1)| |b-a-1|
// ...... ......... .... ...... ........ .....
// |Fn-b+2| |0 . 1. 0| |Fn-b+1| |F(1) | |F(0) | |0 |
// |Fn-b+1| |0 ... 1 0| |Fn-b | |F(0) | |F(-1) | |NaN |
// However, we can solve for F(n+1), which also gives us F(n)
//
// F(n+1) = ( F(n+1-a) + F(n+1-b) ) % m
//
// |Fn+1 | = |0 . 1 . 1| * |Fn | = A^n * |F(b-1)| = A^n * |b-1|
// |Fn | |1 0 ... 0| |Fn-1 | |F(b-2)| |b-2|
// |Fn-1 | |0 1 ... 0| |Fn-2 | |F(b-3)| |b-3|
// ...... ......... .... ...... ...
// |Fn-a+2| |0 . 1 . 0| |Fn-a+1| |F(b-a)| |b-a|
// ...... ......... .... ...... ...
// |Fn-b+3| |0 . 1. 0| |Fn-b+2| |F(1) | |1 |
// |Fn-b+2| |0 ... 1 0| |Fn-b+1| |F(0) | |0 |
//
// From second row:
// F(n) = summation [i=0..b-1] { A^n[1, i] * (b-1-i) }
// At a=1 and b=2
//
// |Fn+1 | = |1 1| * |Fn | = A^n * |F(1)| = A^n * |1|
// |Fn | |1 0| |Fn-1 | |F(0)| |0|
//
// F(n) = A^n[1, 0] * 1 + A^n[1, 1] * 0
// = A^n[1, 0]
for (char ch : n.toCharArray()) {
mc.exponentiate(10, m);
int d = ch - '0';
if (d > 0) {
// TODO, Cache ma^d (only 10 possibilities)
mt.set(ma).exponentiate(d, m);
mc.cross(mt, m);
}
}
return mc.a10;
}
/**
* Fast Matrix Exponentiation, any a, b offset
*/
public static long fibbmod12(String n, long m, int a, int b) {
assert a > 0 && b > 0;
if (Objects.equals(n, "0")) return 0;
if (Objects.equals(n, "1")) return 1;
int s = Math.max(a, b);
if (n.length() <= 9 && Integer.parseInt(n) < s) return Integer.parseInt(n);
var ma = new Matrix(s, s);
ma.set(0, a - 1, 1);
ma.set(0, b - 1, 1);
for (int i = 1; i < s; i++) ma.set(i, i - 1, 1);
var mc = new Matrix(s, s).initIdentity();
var mt = new Matrix(s, s);
for (char ch : n.toCharArray()) {
mc.exponentiate(10, m);
int d = ch - '0';
if (d > 0)
mc.cross(mt.set(ma).exponentiate(d, m), m);
}
long answer = 0;
for (int i = 0; i <= b - 1; i++)
answer = (answer + mc.get(1, i) * (b - 1 - i)) % m;
return answer;
}
/**
* Fast Matrix Exponentiation, LargeNumber
*/
public static int fibbmod13(LargeNumber n, int m) {
if (n.digits.length == 1 && n.digits[0] <= 1) return n.digits[0];
var ma = new Matrix22(1, 1, 1, 0);
var mc = new Matrix22(1, 0, 0, 1);
var mt = new Matrix22(0, 0, 0, 0);
for (int digit : n.digits) {
mc.exponentiate(n.base, m);
if (digit != 0)
mc.cross(mt.set(ma).exponentiate(Integer.toUnsignedLong(digit), m), m);
}
return mc.a10;
}
/**
* Fast Matrix Exponentiation, LargeNumber, any a, b offset
*/
public static long fibbmod14(LargeNumber n, long m, int a, int b) {
assert a > 0 && b > 0;
int s = Math.max(a, b);
if (n.digits.length == 1 && n.digits[0] < s) return n.digits[0];
var ma = new Matrix(s, s);
ma.set(0, a - 1, 1);
ma.set(0, b - 1, 1);
for (int i = 1; i < s; i++) ma.set(i, i - 1, 1);
var mc = new Matrix(s, s).initIdentity();
var mt = new Matrix(s, s);
for (int digit : n.digits) {
mc.exponentiate(n.base, m);
if (digit != 0)
mc.cross(mt.set(ma).exponentiate(Integer.toUnsignedLong(digit), m), m);
}
long answer = 0;
for (int i = 0; i <= b - 1; i++)
answer = (answer + mc.get(1, i) * (b - 1 - i)) % m;
return answer;
}
/**
* Fast Matrix Exponentiation, any a, b offset, factor optimization
*/
public static long fibbmod15(long n, long m, int a, int b) {
assert a > 0 && b > 0;
int s = Math.max(a, b);
if (n < s) return (int) n;
int l = Math.min(a, b);
if (s % l != 0) return fibbmod10(n, m, a, b);
// Assuming, that F[i] = i for every i < s and l divides s
// Then, let s = l * k, where k is an integer
// |Fn | = |1 0 ... 1| * |Fn-l | = A^n-1 * |F((k-1)l)| = A^n-1 * |(k-1)l|
// |Fn-l | |1 0 ... 0| |Fn-2l| |F((k-2)l)| |(k-2)l|
// |Fn-2l | |0 1 ... 0| |Fn-3l| |F((k-3)l)| |(k-3)l|
// ......... ......... ..... ......... ,,,,,,
// |Fn-(k-1)l| |0 ... 1 0| |Fn-kl| |F(0) | |0 |
//
// Fn = summation [i=0..b-1] { A^n-1[0, i] * (k-1-i)l }
int k = s / l;
var ma = new Matrix(k, k);
ma.set(0, 0, 1);
ma.set(0, k - 1, 1);
for (int i = 1; i < k; i++) ma.set(i, i - 1, 1);
ma.exponentiate(n - 1, m);
long answer = 0;
for (int i = 0; i <= b - 1; i++)
answer = (answer + ma.get(0, i) * (k - 1 - i) * l) % m;
return answer;
}
/**
* Print various objects
*/
static void prt(Object... os) {
for (Object o : os)
if (o instanceof Float || o instanceof Double) System.out.printf("%.3f", o);
else System.out.print(o + " ");
System.out.println();
}
/**
* Print time taken and value calculated by a version of fibbmod
*/
static void present(String title, Supplier<Number> fibbmod) {
prt(title + ":");
prt(" Time: ", timeit(() -> prt(" Value:", fibbmod.get())), "sec");
}
static <T> void entertain(String title, T i, Function<T, Number> fibbmod) {
present(title, () -> fibbmod.apply(i));
}
static <T, U> void entertain(String title, T i1, U i2, BiFunction<T, U, Number> fibbmod) {
present(title, () -> fibbmod.apply(i1, i2));
}
interface TriFunction<T, U, V, R> {
R apply(T t, U u, V v);
}
// Kotlin is much better T-T than Java
static <T, U, V> void entertain(String title, T i1, U i2, V i3, TriFunction<T, U, V, Number> fibbmod) {
present(title, () -> fibbmod.apply(i1, i2, i3));
}
interface QuadFunction<T, U, V, W, R> {
R apply(T t, U u, V v, W w);
}
static <T, U, V, W> void entertain(String title, T i1, U i2, V i3, W i4, QuadFunction<T, U, V, W, Number> fibbmod) {
present(title, () -> fibbmod.apply(i1, i2, i3, i4));
}
/**
* Find the optimal value of provided fibbmod which can be calculated under 1 second
*/
static <T> double optimize(Function<Double, T> argument, Function<T, ?> fibbmod) {
for (double l = 10d, f = 1.05d; l < Double.MAX_VALUE; l *= f) {
double time;
try {
T args = argument.apply(l);
time = timeit(() -> fibbmod.apply(args));
} catch (UnsupportedOperationException e) {
prt("Function reached the max input it can process before running out of time.", e.getMessage());
return 0;
} catch (StackOverflowError ignored) {
prt("Stack Overflown: Allocate more memory for stack.");
return 0;
}
// prt(n, time);
if (f < 1 && time <= 1) return l;
if (time > 1) f = 0.95;
}
prt("Function reached further than the optimize function's capacity, which is", Double.MAX_VALUE);
return 0d;
}
/**
* Find out the time required to execute the function
*/
static double timeit(Runnable r) {
var t = System.nanoTime();
r.run();
return (System.nanoTime() - t) / 1000000000.0;
}
static <T> T readLine(String type, Scanner sc, Function<String, T> parse) {
prt("Please enter", type, ":");
do {
try {
return parse.apply(sc.nextLine());
} catch (Exception e) {
prt("The input format is wrong (", e.getMessage(), ").");
prt("Please try again:");
}
} while (true);
}
static final Pattern csd = Pattern.compile("\\s*\\d+(?:\\s*,\\s*\\d+)*\\s*");
static final Pattern num = Pattern.compile("\\d+");
static String inputString(String type, Scanner sc, Pattern p) {
return readLine(type, sc, s -> {
if (!csd.matcher(s).matches()) throw new InputMismatchException();
return s;
});
}
static int inputInt(String type, Scanner sc) {
return readLine(type, sc, Integer::parseInt);
}
static long inputLong(String type, Scanner sc) {
return readLine(type, sc, Long::parseLong);
}
static BigInteger inputBigInt(String type, Scanner sc) {
return new BigInteger(readLine(type, sc, Function.identity()));
}
static int[] inputIntArray(String type, Scanner sc) {
return Arrays.stream(inputString(type, sc, csd).split(",")).map(String::trim).mapToInt(Integer::parseInt).toArray();
}
static LargeNumber inputLarNum(String type, Scanner sc) {
prt("Please enter digits for as long as you like :");
return new LargeNumber(sc);
}
static void menu(String menu, Scanner sc, Runnable... items) {
prt(menu);
int choice = readLine("an option", sc, Integer::parseInt);
if (choice < 0 || choice >= items.length) choice = 0;
items[choice].run();
}
public static void main(String... a) {
// for (int i = 0; i < 150; i++) {
//// prt(i, fibbmod3(i, 10), fibbmod15(i, 10, 1, 2));
//// prt(i, fibbmod10(i, 10, 3, 7), fibbmod12(("" + i), 10, 3, 7), fibbmod14(new LargeNumber("" + i), 10, 3, 7), fibbmod15(i, 10, 3, 7));
// }
// if (true) return;
try (Scanner sc = new Scanner(new InputStreamReader(System.in))) {
while (true) {
prt("Welcome to FibbMod Benchmarks!");
String fibbModMenu = """
Choose a FibbMod Version:
[ 1] -> Simple Recursion
[ 2] -> Recursion with Memoization
[ 3] -> Simple Looping
[ 4] -> Looping with Dictionary
[ 5] -> LwD over BigInteger
[ 6] -> LwD over LargeNumber
[ 7] -> LwDoLN w/o Modulus
[ 8] -> LwDoLN K Offset
[ 9] -> Fast Matrix Exponentiation
[10] -> FME, [a,b] Offset
[11] -> FME, String input
[12] -> FME, String, [a,b] Offset
[13] -> FME, LargeNumber
[14] -> FME, LargeNumber, [a,b] Offset
[15] -> FME, [a,b] Offset, factor
[ 0] -> Back
""";
menu("""
Choose an option:
[1] -> Calculate FibbMod
[2] -> Display preexisting benchmarks
[3] -> Optimize FibbMod
[4] -> Test sanity of all implementations
[0] -> Exit
""", sc,
() -> System.exit(0),
() -> menu(fibbModMenu, sc,
() -> {
},
() -> entertain("fibbmod[01]", inputLong("the value of N (long)", sc), inputLong("the value of M (long)", sc), FibbMod::fibbmod1),
() -> entertain("fibbmod[02]", inputLong("the value of N (long)", sc), inputLong("the value of M (long)", sc), FibbMod::fibbmod2),
() -> entertain("fibbmod[03]", inputLong("the value of N (long)", sc), inputLong("the value of M (long)", sc), FibbMod::fibbmod3),
() -> entertain("fibbmod[04]", inputLong("the value of N (long)", sc), inputLong("the value of M (long)", sc), FibbMod::fibbmod4),
() -> entertain("fibbmod[05]", inputBigInt("the value of N (BigInteger)", sc), inputLong("the value of M (long)", sc), FibbMod::fibbmod5),
() -> entertain("fibbmod[06]", inputIntArray("the value of N (CommaSeparatedDigits)", sc), inputInt("the value of M (int)", sc), FibbMod::fibbmod6),
() -> entertain("fibbmod[07]", inputIntArray("the value of N (CommaSeparatedDigits)", sc), inputInt("the value of M", sc), FibbMod::fibbmod7),
() -> entertain("fibbmod[08]", inputIntArray("the value of N (CommaSeparatedDigits)", sc), inputInt("the value of M", sc), inputInt("the value of K offset", sc), FibbMod::fibbmod8),
() -> entertain("fibbmod[09]", inputLong("the value of N (long)", sc), inputInt("the value of M", sc), FibbMod::fibbmod9),
() -> entertain("fibbmod[10]", inputLong("the value of N (long)", sc), inputLong("the value of M", sc), inputInt("the value of a", sc), inputInt("the value of b", sc), FibbMod::fibbmod10),
() -> entertain("fibbmod[11]", inputString("the value of N (String)", sc, num), inputInt("the value of M", sc), FibbMod::fibbmod11),
() -> entertain("fibbmod[12]", inputString("the value of N (String)", sc, num), inputLong("the value of M", sc), inputInt("the value of a", sc), inputInt("the value of b", sc), FibbMod::fibbmod12),
() -> entertain("fibbmod[13]", inputLarNum("the value of N (LargeNumber)", sc), inputInt("the value of M", sc), FibbMod::fibbmod13),
() -> entertain("fibbmod[14]", inputLarNum("the value of N (LargeNumber)", sc), inputLong("the value of M", sc), inputInt("the value of a", sc), inputInt("the value of b", sc), FibbMod::fibbmod14),
() -> entertain("fibbmod[14]", inputLong("the value of N (long)", sc), inputLong("the value of M", sc), inputInt("the value of a", sc), inputInt("the value of b", sc), FibbMod::fibbmod15)
),
() -> {
prt("fibbmod1 (41,10) [2] =", timeit(() -> fibbmod1(41, 10)));
prt("fibbmod2 (4533731, 10) [7] =", timeit(() -> fibbmod2(1903848, 10)));
prt("fibbmod3 (213998329, 10) [9] =", timeit(() -> fibbmod3(234300455, 10)));
prt("fibbmod4 (2^63-1, 10) [18] =", timeit(() -> fibbmod4(Long.MAX_VALUE, 10)));
prt("fibbmod5 (2^(2^31-1), 10) [10^8] =", timeit(() -> fibbmod5(BigInteger.valueOf(2).pow(2147483647 - 1), 10)));
prt("fibbmod6 (2^32^137256367, 10) [10^10^8] =", timeit(() -> fibbmod6(dtiax(137256367), 10)));
prt("fibbmod7 (2^32^137945231, 10) [10^10^8] =", timeit(() -> fibbmod7(dtiax(137945231), 10)));
prt("fibbmod8 (2^32^137945231, 10) [10^10^8] =", timeit(() -> fibbmod8(dtiax(137945231), 10, 2)));
prt("fibbmod9 (2^63-1, 10) [18] =", timeit(() -> fibbmod9(Long.MAX_VALUE, 10)));
prt("fibbmod10(2^63-1, 10) [18] =", timeit(() -> fibbmod10(Long.MAX_VALUE, 10, 1, 2)));
prt("fibbmod11(2^26258536, 10) [10^6] =", timeit(() -> fibbmod11("1345", 10)));
prt("fibbmod12(2^26258536, 10) [10^6] =", timeit(() -> fibbmod12("1345", 10, 1, 2)));
prt("fibbmod13(10^9^2180802.167, 10) [10^10^6] =", timeit(() -> fibbmod13(dtlnx(2180802.167), 10)));
},
() -> menu(fibbModMenu, sc,
() -> {
},
() -> prt("fibbmod[01] = ", optimize(FibbMod::dtl, n -> fibbmod1(n, 10))),
() -> prt("fibbmod[02] = ", optimize(FibbMod::dtl, n -> fibbmod2(n, 10))),
() -> prt("fibbmod[03] = ", optimize(FibbMod::dtl, n -> fibbmod3(n, 10))),
() -> prt("fibbmod[04] = ", optimize(FibbMod::dtl, n -> fibbmod4(n, 10))),
() -> prt("fibbmod[05] = ", optimize(FibbMod::dtbix, n -> fibbmod5(n, 10))),
() -> prt("fibbmod[06] = ", optimize(FibbMod::dtiax, n -> fibbmod6(n, 10))),
() -> prt("fibbmod[07] = ", optimize(FibbMod::dtiax, n -> fibbmod7(n, 10))),
() -> prt("fibbmod[08] = ", optimize(FibbMod::dtiax, n -> fibbmod8(n, 10, 2))),
() -> prt("fibbmod[09] = ", optimize(FibbMod::dtl, n -> fibbmod9(n, 10))),
() -> prt("fibbmod[10] = ", optimize(FibbMod::dtl, n -> fibbmod10(n, 10, 1, 2))),
() -> prt("fibbmod[11] = ", optimize(FibbMod::dtsx, n -> fibbmod11(n, 10))),
() -> prt("fibbmod[12] = ", optimize(FibbMod::dtsx, n -> fibbmod12(n, 10, 1, 2))),
() -> prt("fibbmod[13] = ", optimize(FibbMod::dtlnx, n -> fibbmod13(n, 10))),
() -> prt("fibbmod[14] = ", optimize(FibbMod::dtlnx, n -> fibbmod14(n, 10, 1, 2))),
() -> prt("fibbmod[15] = ", optimize(FibbMod::dtl, n -> fibbmod15(n, 10, 1, 2)))
),
() -> {
var fibbmods = List.<BiFunction<Integer, Integer, Number>>of(
FibbMod::fibbmod1,
FibbMod::fibbmod2,
FibbMod::fibbmod3,
FibbMod::fibbmod4,
(n, m) -> fibbmod5(dtbi(n), m),
(n, m) -> fibbmod6(dtia(n), m),
(n, m) -> fibbmod7(dtia(n), m),
(n, m) -> fibbmod8(dtia(n), m, 2),
FibbMod::fibbmod9,
(n, m) -> fibbmod10(n, m, 1, 2),
(n, m) -> fibbmod11(dts(n), m),
(n, m) -> fibbmod12(dts(n), m, 1, 2),
(n, m) -> fibbmod13(dtln(n), m),
(n, m) -> fibbmod14(dtln(n), m, 1, 2),
(n, m) -> fibbmod15(dtl(n), m, 1, 2)
);
IntStream.range(5, 11).map(i -> i * 2).boxed()
.flatMap(i -> IntStream.range(2, 10).boxed().map(j -> Map.entry(i, j)))
.map(e -> Map.entry(e, fibbmods.stream().map(f -> f.apply(e.getKey(), e.getValue()).longValue()).toList()))
.forEach(e -> {
var set = new HashSet<>(e.getValue());
if (set.size() != 1) {
prt("Inconsistency found for " + e.getKey());
prt(e.getValue(), set);
}
});
}
);
}
}
/*
// The maximum possible with 12 g ram
int[] digits = new int[1025507324];
digits[0]=1;
prt("time(6)(2^32^1025507323,10) =", timeit(() -> fibbmod6(digits, 10)));
*/
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment