标签: factorization

任何人都可以指向一个库/代码,允许我在python(numpy)中对Cholesky分解进行低级更新吗？Matlab将此功能作为一种称为"cholupdate"的功能提供.LINPACK也有这个功能,但它(据我所知)尚未移植到LAPACK,因此不能用于scipy.

我发现scikits.sparse提供了一个基于CHOLMOD的类似函数,但我的矩阵很密集.

有没有可用于python的代码,'cholupdate'的功能与numpy兼容？

谢谢!

可能重复:
有效地查找数字的所有除数

这更像是一个效率问题,而不是通用的"找到一种方法",但在得到一些奇怪的结果后,我想看看是否有人可以告诉我为什么最后一种方式如此低效:

方式1:蛮力,没有优化

    public static List<int> proper_divisors(int x)
    {
        List<int> toreturn = new List<int>();
        for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
        {
            if (x % i == 0)
            {
                toreturn.Add(i);
                toreturn.Add(x / i);
            }
        }
        if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
        {
            toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
        }

        return toreturn;
    }

方式2:与之前相同,但这一次,检查它是否为第一个(因为这些情况占用了大部分时间,使用miller-rabin进行初步检查)

        public static List<int> proper_divisors(int x)
    {
        List<int> toreturn = new List<int>();
        if (!isprime(x))
        {
            for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++) …

实际上,给定N a(可能非常大)偶数,我想找到N = F*R,其中gcd(F,R)= 1,F> R,F尽可能小(因为我将完全保理F).问题的核心是找到最大的除数R,其中R <sqrt(N).

例如,N = 36应该给出F = 9和R = 4.请注意,R不一定是素数,也不是素数.请注意,我不考虑N.对F和R的唯一限制是它们是相对素数.

这是我的快速和天真的版本,它正在工作:

def factor_partial(N):
    for R in xrange(int(math.sqrt(N)),1,-1):
        if N%R == 0 and gcd(R,N/R) == 1:
            return N/R, R

我想象的另一种方法是按顺序查找除数,并沿途移除任意多个非除数.就像是:

def factor_partial(N):
    i = range(2, int(sqrt(N)) + 1)
    while i:
        if N % i[0] != 0:
            remove_multiples(i, i[0]) #without removing i[0]
        else:
            if gcd(i[0], N/i[0]) == 1:
                R = i[0]
        i.pop(0) #remove i[0]

    return N/R, R

我认为这将是缓慢和内存密集的,但也许如果i是生成器它可能是有效的.我没有太多使用发电机.

我可以改进第一个版本吗？第二个版本是否可行(我将如何做)？有一种完全不同的方法更好吗？

在python,c或pseudocode中寻找答案.

这是一个关于数论的课程.我正在实施基于Pocklington的素性测试.虽然我需要一个分解算法,但我们还没有研究过任何一个,我可能不会使用像我的班级范围之外的二次筛子.我正在寻找提出问题的具体帮助.

当按照维基百科上的轮分解过程进行操作时，我似乎无意中遇到了一个问题：如果我尝试构建 2-3-5-7 轮，则素数 331 被视为合数。

采用2-3-5-7轮，2*3*5*7=210。因此，我设置了一个包含 210 个槽位的圆圈，并顺利完成步骤 1-7。然后我进入第8步，划掉所有素数倍数的辐条，最终划掉以121为根的辐条，121是11的倍数，11是素数。对于以 121 为根的辐条，121 + 210 = 331。不幸的是，331 是一个质数。

维基百科上的程序不正确吗？

或者我是否误解了该过程，应该只删除 2、3、5 和 7 的倍数的辐条，而不删除任何小于 210 的其他素数？

对于给定数n(我们知道n = p ^ a*q ^ b,对于一些素数p,q和一些整数a,b)和给定数量φ(n)(http://en.wikipedia. org/wiki/Euler%27s_totient_function)找到p,q,a和b.

捕获的是n,并且φ(n)具有大约200个数字,因此算法必须非常快.这似乎是非常难的问题,我完全不知道如何使用φ(n).

怎么解决这个问题？

关于如何实现分解有很多问题,但是对于生产用途,我宁愿使用开源库来获得高效的东西并立即进行测试.我正在寻找的方法如下:

static int[] getPrimeFactors(int n)

对于n = 12,它将返回{2,2,3}

库也可能具有处理long或甚至BigInteger类型的重载

问题不是关于特定的应用程序,而是关于有一个处理这个问题的库.许多人认为根据数字的范围需要不同的实现,在这方面,我希望库在运行时选择最合理的方法.

通过高效我并不意味着"世界上最快"(我不会在JVM上工作......),我只是意味着在一秒而不是一小时内处理int和long range.

在我的matlab代码中,我必须处理某个给定矩阵的Cholesky分解.我通常要求chol(A,'lower')产生较低的三角形因子.

现在,检查我的代码,profiler显然函数chol非常耗时,特别是如果输入矩阵的大小变大.

因此,我想知道,如果内置chol函数有任何有价值的替代方案.

我一直在想LAPACK图书馆,即spptrf功能.它是否可用MATLAB？

任何提示或支持都非常受欢迎.

编辑

举个例子,探查器检索这些信息:

哪里Coh_u有大小(1395*1395).它也chol被称为4000时代,因为我需要4000不同配置的胆怯因素.

我正在寻找Java API来进行快速素性测试和大数字因子分解.任何指针都对我很有帮助.

更新

我找到的资源是:

• BigInteger - 没有因子分解
• Primes - 处理整数
• LargeInteger - 没有因子分解

我期待使用Elliptic Curve Factorization或Quadratic Sieve的API .

另一种资源:使用椭圆曲线法进行分解.

限制:10000位数.

我在我找到的网站上做了这个问题(项目Euler),并且有一个问题涉及找到一个数字的最大素数因子.我的解决方案失败了很多,所以我想知道如何简化这段代码？

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in range(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    for i in range(1, number + 1):
        if i!=1 and i!=2 and i!=number:
            if number%i == 0:
                prime = False
    return prime

def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    prime_factors …

我想尝试实现Yun的多项式无平方因子分解算法.来自维基百科(f是多项式):

a0 = gcd(f, f'); b1 = f/a0; c1 = f'/a0; d1 = c1 - b1'; i = 1
repeat
ai = gcd(bi, di); bi+1 = bi/ai; ci+1 = di/ai; i = i + 1; di = ci - bi'
until b = 1

但是,我不确定第二步.我想将它用于具有整数系数的多项式(不需要monic或primitive).是否有可能b1 = f/a0只使用整数实现除法？

我找到了合成分部的代码:

def extended_synthetic_division(dividend, divisor):
    '''Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.'''
    # dividend and divisor are both polynomials, which …