java遇到超大计算的一道题,不知道如何快速计算出来

919359733

如图中的问题
自己写的g(1000000) 电脑都快爆了

lvxuyang

超过20位的考虑截取后20位进行相关运算试试呢？

namedlxd

快速幂运算

zzs52547

建议楼主换一台配置好点的电脑

h88782481

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))
我的奔騰四處理器就路過看一下。

爱飞的猫

[Java] 纯文本查看 复制代码

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-5 23:52
[mw_shl_code=java,true]package moe.jixun;

import java.math.BigInteger;

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[threadCount];

        for(int i = 0; i < threadCount; i++) {
            threads[i] = new ThreadRunner(source);
            threads[i].start();
        }

        for(int i = 0; i < threadCount; i++) {
            try {
                threads[i].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[0], 10);
        }
        AlgoMain inst = new AlgoMain(threadCount);
        inst.calc(10);
        inst.calc(1000);
        inst.calc(1000000);
        inst.calc((long)Math.pow(10, 10));
    }
}

再来个多线程版… 以及下面不适用大数库的优化版（应该不会溢出吧）…

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[threadCount];

        for (int i = 0; i < threadCount; i++) {
            threads[i] = new ThreadRunner(source);
            threads[i].start();
        }

        for (int i = 0; i < threadCount; i++) {
            try {
                threads[i].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[0], 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)); // ???
    }
}

最后一问应该可以用简单地线性回归计算吧，不太懂机器学习…

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([10, 100, 1000, 10000, 100000, 1000000]).reshape((-1, 1))
time = np.array([3, 11, 17, 64, 657, 8222]).reshape((-1, 1))

model = LinearRegression().fit(n, time)

# 82384373.10720266ms = 22.88 小时
print(model.predict([[math.pow(10,10)]]))

xtcn

要更快速，就要用数学方法，而不是只用机械（电子机械）循环...

sitiger

pythoner walks away