小编Peđ*_*zić的帖子

什么是Java 7中的方法的复杂性pow，并isProbablePrime在BigInteger上课吗？

我知道 Rabin 测试的简单实现是 O(k(log(n))^3) 复杂度，并且可以通过结合Schönhage-Strassen 算法来快速乘以长整数来降低复杂度。

假设我有两个计算复杂性:

1. O(k * M(n))- 模幂运算的计算复杂度,其中k指数位n的数量是位数,并且M(n)是牛顿除法算法的计算复杂度.

2. O(log^6(n)) - 算法的计算复杂性.

如何确定这两种复杂性中哪一种不那么"昂贵"？事实上,符号M(n)是让我最困惑的.

我有几个Java代码,我希望测量经验计算的复杂性.有一个trend-prof工具,它作为输入编译C/C++程序.

趋势教程是否有类似的工具作为输入编译的Java程序？

我有两个简单的java代码.第一个定义恒定功率为power = a.pow(b);

import java.math.BigInteger;    
public class FermatOne    
{    
    public static void main(String[] args)    
    {    
         BigInteger a = new BigInteger ("2");    
         BigInteger k = new BigInteger ("15");    
         BigInteger c = new BigInteger ("1");    
         int b = 332192810;    
         BigInteger n = new BigInteger ("2");    
         BigInteger power;    
         power = a.pow(b);    
         BigInteger exponent;    
         exponent = k.multiply(power);    
         BigInteger mod;    
         mod = exponent.add(c);    
         BigInteger result = n.modPow(exponent,mod);    
         System.out.println("Result is  ==> " + result);    
     }    
}

第二个定义恒定功率为power = BigInteger.ONE.shiftLeft(b)

import java.math.BigInteger;    
public class FermatOne    
{    
    public …

这是一个 Haskell 代码，用于计算一个不起作用的数字的合成。合数 n 的合数是直到并包括 n 的所有合数的乘积。这段代码有什么问题？

module Compositorial where

import Data.Array.ST
import Data.Array.Unboxed
import Data.Array.Base

-- multiply all composite numbers <= n
-- Use a sieve for a fast compositeness test, and multiply in a tree-like fashion
compositorial :: Int -> Integer
compositorial n = treeProd (sieve n) 4 n

-- Sieve of Eratosthenes, basic
sieve :: Int -> UArray Int Bool
sieve end = runSTUArray $ do
    ar <- newArray (0,end) False
    let mark step idx
            | idx …