java遇到超大计算的一道题,不知道如何快速计算出来
本帖最后由 919359733 于 2020-11-6 16:52 编辑如图中的问题
自己写的g(1000000) 电脑都快爆了 超过20位的考虑截取后20位进行相关运算试试呢？ 快速幂运算 建议楼主换一台配置好点的电脑{:1_918:} public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(fastPower(5,2,10000007));
}
public static long fastPower(long a,long b,long mod) {
long ans=1;
while(b!=0) {
if((b&1)==1)
ans=ans*a%mod;
a=a*a;
b=b>>1;
}
return ans;
}
快速幂算法 g(10^10)≈g(f(10))
我的奔騰四處理器就路過看一下。 本帖最后由 jixun66 于 2020-11-6 07:41 编辑
package moe.jixun;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
Main inst = new Main();
inst.calc(1000000);
inst.calc(1000000);
inst.calc(1000000);
inst.calc(1000000);
inst.calc((long)Math.pow(10, 10));
}
private void calc(long i) {
long now = System.currentTimeMillis();
BigInteger result = this.g(i);
long delta = System.currentTimeMillis() - now;
System.out.println("g(" + i + ") = " + result + " 用时 " + delta + "ms");
}
private BigInteger f(long n) {
BigInteger result = BigInteger.ZERO;
for(BigInteger i = BigInteger.valueOf(n); i.compareTo(BigInteger.ZERO) != 0; i = i.subtract(BigInteger.ONE)) {
BigInteger subTerm = i.modPow(i, divider);
result = result.add(subTerm);
}
return result;
}
static private final BigInteger divider = BigInteger.valueOf(10).pow(10);
private BigInteger g(long i) {
return f(i).mod(divider);
}
}
放弃完整精度，用大数的 modPow 吧。
10^6 计算用大概 4 秒，10^10 大概是 10^6 的 10000 倍，近 11 个小时。 本帖最后由 jixun66 于 2020-11-9 01:31 编辑
jixun66 发表于 2020-11-5 23:52
package moe.jixun;
import java.math.BigInteger;
```java
package moe.jixun;
import java.math.BigInteger;
class BIStore {
private final Object lockValue = new Object();
private final Object lockSum = new Object();
private BigInteger sum = BigInteger.ZERO;
private BigInteger value;
BIStore(BigInteger max) {
this.value = max.add(BigInteger.ONE);
}
public BigInteger next(){
synchronized (lockValue) {
value = value.subtract(BigInteger.ONE);
return value;
}
}
public void add(BigInteger toAdd) {
synchronized (lockSum) {
this.sum = this.sum.add(toAdd);
}
}
public BigInteger getSum() {
return sum;
}
}
class ThreadRunner extends Thread {
static private final BigInteger divider = BigInteger.valueOf(10).pow(10);
private final BIStore store;
ThreadRunner(BIStore store) {
this.store = store;
}
@Override
public void run() {
for(BigInteger value = store.next(); value.compareTo(BigInteger.ZERO) > 0; value = store.next()) {
BigInteger toAdd = value.modPow(value, divider);
store.add(toAdd);
}
}
}
class AlgoMain {
private final int threadCount;
public AlgoMain(int threadCount) {
this.threadCount = threadCount;
}
static private final BigInteger divider = BigInteger.valueOf(10).pow(10);
public BigInteger f(long n) {
BIStore source = new BIStore(BigInteger.valueOf(n));
ThreadRunner[] threads = new ThreadRunner;
for(int i = 0; i < threadCount; i++) {
threads = new ThreadRunner(source);
threads.start();
}
for(int i = 0; i < threadCount; i++) {
try {
threads.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
return source.getSum();
}
private BigInteger g(long i) {
return f(i).mod(divider);
}
public void calc(long i) {
System.out.println("i = " + i);
long now = System.currentTimeMillis();
BigInteger result = this.g(i);
long delta = System.currentTimeMillis() - now;
System.out.println("g(" + i + ") = " + result + " 用时 " + delta + "ms");
}
}
public class Main {
public static void main(String[] args) {
// 线程数量
int threadCount = 2;
if (args.length > 0) {
threadCount = Integer.valueOf(args, 10);
}
AlgoMain inst = new AlgoMain(threadCount);
inst.calc(10);
inst.calc(1000);
inst.calc(1000000);
inst.calc((long)Math.pow(10, 10));
}
}
```
再来个多线程版… 以及下面不适用大数库的优化版（应该不会溢出吧）…
```java
package moe.jixun;
class BIStore {
public static final long divider = (long) Math.pow(10, 10);
private final Object lockValue = new Object();
private final Object lockSum = new Object();
private long sum = 0L;
private long value;
BIStore(long max) {
this.value = max;
}
public long next() {
synchronized (lockValue) {
return value--;
}
}
public static long modMul(long a, long b) {
if (a == 0 || b < divider / a)
return (a * b) % divider;
long sum = 0;
while (b > 0) {
if ((b & 1) == 1) {
sum = (sum + a) % divider;
}
a = (a << 1) % divider;
b >>= 1;
}
return sum;
}
public static long selfPow(long base) throws Exception {
long exponent = base;
long result = 1L;
while (exponent > 0) {
if ((exponent & 1) == 1) {
result = BIStore.modMul(result, base);
}
exponent = exponent >> 1;
base = BIStore.modMul(base, base);
}
return result;
}
public void add(long toAdd) {
synchronized (lockSum) {
// 34 位
this.sum = (this.sum + toAdd) % divider;
}
}
public long getSum() {
return sum;
}
}
class ThreadRunner extends Thread {
private final BIStore store;
ThreadRunner(BIStore store) {
this.store = store;
}
@Override
public void run() {
for (long i = store.next(); i > 0L; i = store.next()) {
long toAdd = 0;
try {
toAdd = BIStore.selfPow(i);
} catch (Exception e) {
e.printStackTrace();
}
store.add(toAdd);
}
}
}
class AlgoMain {
private final int threadCount;
public AlgoMain(int threadCount) {
this.threadCount = threadCount;
}
public long f(long n) {
BIStore source = new BIStore(n);
ThreadRunner[] threads = new ThreadRunner;
for (int i = 0; i < threadCount; i++) {
threads = new ThreadRunner(source);
threads.start();
}
for (int i = 0; i < threadCount; i++) {
try {
threads.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
return source.getSum();
}
private long g(long i) {
return f(i) % BIStore.divider;
}
public void calc(long i) {
long now = System.currentTimeMillis();
long result = this.g(i);
long delta = System.currentTimeMillis() - now;
System.out.println("g(" + i + ") = " + result + " 用时 " + delta + "ms");
}
}
public class Main {
public static void main(String[] args) {
// 线程数量
int threadCount = 2;
if (args.length > 0) {
threadCount = Integer.valueOf(args, 10);
}
AlgoMain inst = new AlgoMain(threadCount);
inst.calc(10); // 405071317
inst.calc(1000); // 9110846700
inst.calc(1000000); // 4077562500
inst.calc((long)Math.pow(10, 10)); // ???
}
}
```
最后一问应该可以用简单地线性回归计算吧，不太懂机器学习…
```py
import math
import numpy as np
from sklearn.linear_model import LinearRegression
# g(10) = 405071317 用时 3ms
# g(100) = 9027641920 用时 11ms
# g(1000) = 9110846700 用时 17ms
# g(10000) = 6237204500 用时 64ms
# g(100000) = 3031782500 用时 657ms
# g(1000000) = 4077562500 用时 8222ms
# g(10000000000) = 2693362500 用时 138432673ms
n = np.array().reshape((-1, 1))
time = np.array().reshape((-1, 1))
model = LinearRegression().fit(n, time)
# 82384373.10720266ms = 22.88 小时
print(model.predict([]))
```
要更快速，就要用数学方法，而不是只用机械（电子机械）循环... pythoner walks away
页:
[1]