70

我编写了一个程序,试图找到 Amicable Pairs。这需要找到数字的适当除数的总和。

这是我目前的sumOfDivisors()方法:

int sumOfDivisors(int n)
{  
    int sum = 1;
    int bound = (int) sqrt(n);
    for(int i = 2; i <= 1 + bound; i++)
    {
        if (n % i == 0)
            sum = sum + i + n / i;
    } 
    return sum;
}

所以我需要做很多分解,这开始成为我应用程序的真正瓶颈。我在 MAPLE 中输入了一个巨大的数字,它以非常快的速度计算出来。

什么是更快的分解算法之一?

4

9 回答 9

112

直接从我对另一个问题的回答中提取。

该方法会起作用,但会很慢。“你的数字有多大?” 确定使用的方法:

于 2010-02-16T16:39:51.557 回答
23

标题(和最后一行)中的问题似乎与问题的实际正文无关。如果您试图找到友好的对,或者计算许多数字的除数之和,那么单独分解每个数字(即使使用最快的算法)绝对是一种低效的方法。

除数和函数, ,σ(n) = (sum of divisors of n)是一个乘法函数: 对于互素的 m 和 n, 我们有σ(mn) = σ(m)σ(n), 所以

σ(p 1 k 1 …p r k r ) = [(p 1 k 1 +1 -1)/(p 1 -1)]…[(p r k r +1 -1)/(p r -1 )]。

因此,您可以使用任何简单的筛子(例如,埃拉托色尼筛子的增强版)来找到最高为 的素数n,并在此过程中对最高为 n 的所有数进行因式分解。(例如,当你做你的筛子时,存储每个 n 的最小素因子。然后你可以n通过迭代来分解任何数字。)这将比使用任何单独的分解算法多次更快(总体上)。

顺便说一句:已经存在几个已知的友好配对列表(例如,请参见此处和MathWorld上的链接)——那么您是想扩展记录,还是只是为了好玩?

于 2010-02-15T16:35:03.200 回答
22

Shor 算法: http ://en.wikipedia.org/wiki/Shor%27s_algorithm

当然你需要一台量子计算机:D

于 2010-02-15T16:17:41.580 回答
13

我建议从 Maple 中使用的相同算法开始,即Quadratic Sieve

  1. 选择你的奇数n进行因式分解,
  2. 选择一个自然数k
  3. 搜索所有p <= k使得k^2不等于(n mod p)以获得因子 base B = p1, p2, ..., pt
  4. r > floor(n)开始搜索至少t+1 个值,使得y^2 = r^2 - n都只有 B 中的因子,
  5. 对于刚刚计算的每个y1y2、 ...、y(t+1),您会生成一个向量v(yi) = (e1, e2, ..., et),其中ei是通过在模 2 上减去指数pi来计算的在彝族
  6. 使用高斯消元法找到一些相加的向量给出一个空向量
  7. x设置为与上一步中找到的yi相关的ri的乘积,并将y设置为 p1^a * p2^b * p3^c * .. * pt^z 其中指数是在因式分解中找到的指数的一半
  8. 计算 d = mcd(xy, n),如果1 < d < nd是 n 的重要因子否则从步骤 2 开始选择更大的 k。

这些算法的问题在于它们确实暗示了数值计算中的很多理论。

于 2010-02-15T16:35:01.130 回答
7

这是 Maple 中的 Integer Factorization 的一篇论文。

“从一些非常简单的指令开始——“在 Maple 中使整数分解更快”——我们结合 Maple 和 C 实现了二次筛分解算法......”

http://www.cecm.sfu.ca/~pborwein/MITACS/papers/percival.pdf

于 2010-02-15T16:12:12.697 回答
6

一个更 2015 C++ 版本 2 27查找表实现 1GB 内存:

#include <iostream.h> // cerr, cout, and NULL
#include <string.h>   // memcpy()
#define uint unsigned __int32
uint *factors;
const uint MAX_F=134217728; // 2^27

void buildFactors(){
   factors=new (nothrow) uint [(MAX_F+1)*2]; // 4 * 2 * 2^27 = 2^30 = 1GB
   if(factors==NULL)return; // not able to allocate enough free memory
   int i;
   for(i=0;i<(MAX_F+1)*2;i++)factors[i]=0;

   //Sieve of Eratosthenese
   factors[1*2]=1;
   factors[1*2+1]=1;
   for(i=2;i*i<=MAX_F;i++){
      for(;factors[i*2] && i*i<=MAX_F;i++);
      factors[i*2]=1;
      factors[i*2+1]=i;
      for(int j=2;i*j<=MAX_F;j++){
         factors[i*j*2]=i;
         factors[i*j*2+1]=j;
      }
   }
   for(;i<=MAX_F;i++){
      for(;i<=MAX_F && factors[i*2];i++);
      if(i>MAX_F)return;
      factors[i*2]=1;
      factors[i*2+1]=i;
   }
}

uint * factor(uint x, int &factorCount){
   if(x > MAX_F){factorCount=-1;return NULL;}
   uint tmp[70], at=x; int i=0;
   while(factors[at*2]>1){
      tmp[i++]=factors[at*2];
      cout<<"at:"<<at<<" tmp:"<<tmp[i-1]<<endl;
      at=factors[at*2+1];
   }
   if(i==0){
      cout<<"at:"<<x<<" tmp:1"<<endl;
      tmp[i++]=1;
      tmp[i++]=x;
   }else{
      cout<<"at:"<<at<<" tmp:1"<<endl;
      tmp[i++]=at;
   }
   factorCount=i;
   uint *ret=new (nothrow) uint [factorCount];
   if(ret!=NULL)
      memcpy(ret, tmp, sizeof(uint)*factorCount);
   return ret;
}

void main(){
   cout<<"Loading factors lookup table"<<endl;
   buildFactors(); if(factors==NULL){cerr<<"Need 1GB block of free memory"<<endl;return;}
   int size;
   uint x=30030;
   cout<<"\nFactoring: "<<x<<endl;
   uint *f=factor(x,size);
   if(size<0){cerr<<x<<" is too big to factor. Choose a number between 1 and "<<MAX_F<<endl;return;}
   else if(f==NULL){cerr<<"ran out of memory trying to factor "<<x<<endl;return;}

   cout<<"\nThe factors of: "<<x<<" {"<<f[0];
   for(int i=1;i<size;i++)
      cout<<", "<<f[i];
   cout<<"}"<<endl;
   delete [] f;

   x=30637;
   cout<<"\nFactoring: "<<x<<endl;
   f=factor(x,size);
   cout<<"\nThe factors of: "<<x<<" {"<<f[0];
   for(int i=1;i<size;i++)
      cout<<", "<<f[i];
   cout<<"}"<<endl;
   delete [] f;
   delete [] factors;
}

更新:或牺牲一些简单性以获得更多的范围刚刚过去 2 28

#include <iostream.h> // cerr, cout, and NULL
#include <string.h>   // memcpy(), memset()

//#define dbg(A) A
#ifndef dbg
#define dbg(A)
#endif

#define uint   unsigned __int32
#define uint8  unsigned __int8
#define uint16 unsigned __int16

uint * factors;
uint8  *factors08;
uint16 *factors16;
uint   *factors32;

const uint LIMIT_16   = 514; // First 16-bit factor, 514 = 2*257
const uint LIMIT_32   = 131074;// First 32-bit factor, 131074 = 2*65537
const uint MAX_FACTOR = 268501119;
//const uint64 LIMIT_64 = 8,589,934,594; // First 64-bit factor, 2^33+1

const uint TABLE_SIZE = 268435456; // 2^28 => 4 * 2^28 = 2^30 = 1GB 32-bit table
const uint o08=1, o16=257 ,o32=65665; //o64=4294934465
// TableSize = 2^37 => 8 * 2^37 = 2^40 1TB 64-bit table
//   => MaxFactor = 141,733,953,600

/* Layout of factors[] array
*  Indicies(32-bit)              i                 Value Size  AFactorOf(i)
*  ----------------           ------               ----------  ----------------
*  factors[0..128]            [1..513]             8-bit       factors08[i-o08]
*  factors[129..65408]        [514..131073]        16-bit      factors16[i-o16]
*  factors[65409..268435455]  [131074..268501119]  32-bit      factors32[i-o32]
*
* Note: stopping at i*i causes AFactorOf(i) to not always be LargestFactor(i)
*/
void buildFactors(){
dbg(cout<<"Allocating RAM"<<endl;)
   factors=new (nothrow) uint [TABLE_SIZE]; // 4 * 2^28 = 2^30 = 1GB
   if(factors==NULL)return; // not able to allocate enough free memory
   uint i,j;
   factors08 = (uint8 *)factors;
   factors16 = (uint16 *)factors;
   factors32 = factors;
dbg(cout<<"Zeroing RAM"<<endl;)
   memset(factors,0,sizeof(uint)*TABLE_SIZE);
   //for(i=0;i<TABLE_SIZE;i++)factors[i]=0;

//Sieve of Eratosthenese
     //8-bit values
dbg(cout<<"Setting: 8-Bit Values"<<endl;)
   factors08[1-o08]=1;
   for(i=2;i*i<LIMIT_16;i++){
      for(;factors08[i-o08] && i*i<LIMIT_16;i++);
dbg(cout<<"Filtering: "<<i<<endl;)
      factors08[i-o08]=1;
      for(j=2;i*j<LIMIT_16;j++)factors08[i*j-o08]=i;
      for(;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
      for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
   }
   for(;i<LIMIT_16;i++){
      for(;i<LIMIT_16 && factors08[i-o08];i++);
dbg(cout<<"Filtering: "<<i<<endl;)
      if(i<LIMIT_16){
         factors08[i-o08]=1;
         j=LIMIT_16/i+(LIMIT_16%i>0);
         for(;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
         for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
      }
   }i--;

dbg(cout<<"Setting: 16-Bit Values"<<endl;)
     //16-bit values
   for(;i*i<LIMIT_32;i++){
      for(;factors16[i-o16] && i*i<LIMIT_32;i++);
      factors16[i-o16]=1;
      for(j=2;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
      for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
   }
   for(;i<LIMIT_32;i++){
      for(;i<LIMIT_32 && factors16[i-o16];i++);
      if(i<LIMIT_32){
         factors16[i-o16]=1;
         j=LIMIT_32/i+(LIMIT_32%i>0);
         for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
      }
   }i--;

dbg(cout<<"Setting: 32-Bit Values"<<endl;)
     //32-bit values
   for(;i*i<=MAX_FACTOR;i++){
      for(;factors32[i-o32] && i*i<=MAX_FACTOR;i++);
      factors32[i-o32]=1;
      for(j=2;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
   }
   for(;i<=MAX_FACTOR;i++){
      for(;i<=MAX_FACTOR && factors32[i-o32];i++);
      if(i>MAX_FACTOR)return;
      factors32[i-o32]=1;
   }
}

uint * factor(uint x, int &factorCount){
   if(x > MAX_FACTOR){factorCount=-1;return NULL;}
   uint tmp[70], at=x; int i=0;
   while(at>=LIMIT_32 && factors32[at-o32]>1){
      tmp[i++]=factors32[at-o32];
dbg(cout<<"at32:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
      at/=tmp[i-1];
   }
   if(at<LIMIT_32){
      while(at>=LIMIT_16 && factors16[at-o16]>1){
         tmp[i++]=factors16[at-o16];
dbg(cout<<"at16:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
         at/=tmp[i-1];
      }
      if(at<LIMIT_16){
         while(factors08[at-o08]>1){
            tmp[i++]=factors08[at-o08];
dbg(cout<<"at08:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
            at/=tmp[i-1];
         }
      }
   }
   if(i==0){
dbg(cout<<"at:"<<x<<" tmp:1"<<endl;)
      tmp[i++]=1;
      tmp[i++]=x;
   }else{
dbg(cout<<"at:"<<at<<" tmp:1"<<endl;)
      tmp[i++]=at;
   }
   factorCount=i;
   uint *ret=new (nothrow) uint [factorCount];
   if(ret!=NULL)
      memcpy(ret, tmp, sizeof(uint)*factorCount);
   return ret;
}
uint AFactorOf(uint x){
   if(x > MAX_FACTOR)return -1;
   if(x < LIMIT_16) return factors08[x-o08];
   if(x < LIMIT_32) return factors16[x-o16];
                    return factors32[x-o32];
}

void main(){
   cout<<"Loading factors lookup table"<<endl;
   buildFactors(); if(factors==NULL){cerr<<"Need 1GB block of free memory"<<endl;return;}
   int size;
   uint x=13855127;//25255230;//30030;
   cout<<"\nFactoring: "<<x<<endl;
   uint *f=factor(x,size);
   if(size<0){cerr<<x<<" is too big to factor. Choose a number between 1 and "<<MAX_FACTOR<<endl;return;}
   else if(f==NULL){cerr<<"ran out of memory trying to factor "<<x<<endl;return;}

   cout<<"\nThe factors of: "<<x<<" {"<<f[0];
   for(int i=1;i<size;i++)
      cout<<", "<<f[i];
   cout<<"}"<<endl;
   delete [] f;

   x=30637;
   cout<<"\nFactoring: "<<x<<endl;
   f=factor(x,size);
   cout<<"\nThe factors of: "<<x<<" {"<<f[0];
   for(int i=1;i<size;i++)
      cout<<", "<<f[i];
   cout<<"}"<<endl;
   delete [] f;
   delete [] factors;
}
于 2015-10-26T21:24:19.800 回答
5

取决于你的数字有多大。如果您正在寻找友好的配对,那么您正在做很多分解,所以关键可能不是尽快分解,而是在不同的调用之间共享尽可能多的工作。为了加快试验划分,您可以查看记忆,和/或预先计算素数,直到您关心的最大数的平方根。获得素因数分解,然后从中计算所有因子的总和,比对每个数字一直循环到 sqrt(n) 更快。

如果您正在寻找非常大的友好对,例如大于 2^64,那么在少数机器上,无论您的因式分解有多快,您都无法通过分解每个数字来做到这一点。您用来寻找候选人的捷径可能会帮助您考虑他们。

于 2010-02-15T16:16:30.017 回答
1

这是截至 2020 年的一个重要的开放数学问题

其他人则从实际的角度回答,对于实践中遇到的问题大小,这些算法很可能接近最优。

然而,我还想强调,更一般的数学问题(在渐近计算复杂度中,即比特数趋于无穷大)完全没有解决。

没有人能够证明什么是最快的可能算法的最小最佳时间。

这显示在 Wikipedia 页面上: https ://en.wikipedia.org/wiki/Integer_factorization该算法还出现在 Wiki 的“计算机科学中未解决问题列表”页面上:https ://en.wikipedia.org/wiki/ List_of_unsolved_problems_in_computer_science

我们所知道的是,我们目前拥有的最好的是通用数字筛。直到 2018 年,我们甚至都没有关于其复杂性的非启发式证明。就要分解的整数的位数而言,该算法的复杂性类似于:

e^{(k + o(1))(n^(1/3) * ln(n)^(2/3)}

如前所述:多项式时间和指数时间不是真正的指数,但它是超多项式。

截至 2020 年,我们甚至还没有证明问题是否是NP 完全的(尽管它显然是 NP,因为验证解决方案所需要做的就是将数字相乘)!尽管人们普遍认为它是 NP 完全的。我们在寻找算法方面不会那么差,不是吗?

于 2020-06-15T17:37:08.623 回答
-2

当然还有 Hal Mahutan 教授的 HAL 算法(2021 年 2 月),它处于因式分解研究的边缘。

请在此处查看最新更新

https://docs.google.com/document/d/1BlDMHCzqpWNFblq7e1F-rItCf7erFMezT7bOalvhcXA/edit?usp=sharing

求解公钥的两个大素数如下...

任何 AxB = 公钥都可以绘制在正 X 轴和 Y 轴上,形成一条连续曲线,其中所有非整数因子求解公钥。当然,这没什么用,只是在这一点上的一个观察。

Hal 的见解是:如果我们坚持只对 A 是整数的点感兴趣,特别是当 A 是整数时 B 出现的点。

当数学家与 B 其余部分的明显随机性或至少缺乏可预测性作斗争时,以前使用这种方法的尝试失败了。

Hal 的意思是,只要 a/b 的比率相同,任何公钥的可预测性都是通用的。基本上,当提供一系列不同的公钥进行分析时,它们都可以被相同地处理,只要它们在处理期间共享相同的点,其中 a/b 是恒定的,即它们共享相同的切线。

看看我画的这张草图,试图解释马胡坦教授在这里发生了什么。

哈尔的洞察力

所以,这是哈尔的天才。Hal 利用功能强大的超级计算机生成一系列哈希表(在图表中,Q、R、S & T)。您可以在左侧的 3 A x B = Key 曲线中看到它们都共享切线 T 和 S(唯一突出显示的部分),但该图显示的是给定任何公钥,在切线相同的曲线,那么您可以共享主持该区域的哈希表。

只是一个技术说明,显然在 AxB= Key 的曲线中,随着 AxB 值的改变,事情会不断变化,所以理论上,映射到哈希表的共享切线会过时,但有趣的是是具有非常大的密钥(具有讽刺意味的是,这使它们更容易破解,因为它们在哈希表有用的地方共享更长的运行时间。)。所以这是个好消息,因为随着因式分解和计算的进步加速,预计密钥大小会变得更大。实际发生的情况是哈希表的可预测性将在字面上“失焦”,因为它们应用的切线开始发散。幸运的是,这不是问题,因为您会跳转到适当映射到新 Tangent 的下一个哈希表。

为了清楚起见,所有生成的公钥将始终使用同一组哈希表,因此这是一种一次性投资,可以在线存储数百万 TB 的查找数据,因为所有密钥都遵循相同的规则切向比。

那么,哈希表如何加速寻找素数。当公钥除以 B 时,哈希表用余数索引。基本上,Hal 是说对于所有密钥,可以查找 A x B 的任何比率。共享相同切线的不同曲线之间的唯一区别是它们需要不同的偏移,由“控制曲线”确定。“控制曲线”是您为其生成适当因子的任意曲线。假设对于“控制曲线”,Key 为 15,而被映射的切线是 B = 5 时,因此 A 为 3,余数为零。在另一个具有相同切线的映射中,假设键现在是 16。我们需要找到相同的切线,B 为 5.33,A 为 3.2。所以 A 的余数是 0.2,

那么哈希表中有什么?由偏移量索引,并且该值始终返回沿 AxB 曲线的距离,您找不到另一个整数 B。Hal 的意思是向前跳是安全的,而不是检查这些数字是否是因子。基本上就是这样。哈尔在曲线上打了个洞,这些洞永远不需要检查,这只会加速整个比赛。

谢谢马胡坦教授!


对于那些仍在关注的人,以下是我们的一些工作笔记:


快速因式分解攻击算法的要点

  • 所有公钥都可以沿着曲线 A x B = 'Key' 表示
  • 这是一个映射所有实数(这是非整数的正确术语吗?)的观察结果,所有实数相乘以等于键......到目前为止没有用
  • 我们只对 A 为整数且 B 均为整数的点感兴趣。
  • 我们可以遍历 A 为整数的整条线。这是一半,但有问题。首先,我们不知道 B 在哪里是整数,而且计算所有点需要太多的处理能力。
  • 我们感兴趣的是预测 B 在哪里也是整数,因此我们想要一种机制能够沿着我们知道 B 绝对仍然是实数(非整数)的曲线“跳跃”。如果我们可以进行足够大的跳跃,那么我们就可以减少所需的处理。

现在按照算法的策略来预测B

  • 另一个观察结果是,对于足够大的“Key”值,当我们逐步改变 A 的整数增量值时,我们观察到 A/B 的比率或切线角将基本保持不变。

  • 这一观察的一个重要方面是,随着 Key 大小的增加,每次迭代的切线保持更加恒定。从根本上说,这意味着任何使用此属性的算法都将随着密钥大小的增加而变得更加高效,这与传统方法相反,传统方法增加密钥大小会使猜测因素成倍增加。这是非常重要的一点……(请尼克详细说明)

  • 算法本身如下

  • 在云上购买足够的存储和处理能力
  • 将问题分解成可以在不同进程上并行运行的部分。为此,我们逐步检查不同的 A 值,并将搜索分配给云中的不同处理器。
  • 对于正在检查的 A 的任何值,使用通用查找表来预测沿曲线移动的安全距离,而无需计算 B 是否为整数
  • 仅检查查找表显示其为整数的概率高到足以保证检查的曲线上的那些位置。

这里的重要概念是,在查找变得不准确(并且失去焦点)之前,A/B(切线)的比率足够接近的任何“键”都可以共享查找表。

(还要注意的是,随着密钥大小的变化,您要么需要一组新的表,要么应该对现有的比率表进行适当的映射以重用它们。)

Nick 另一个非常重要的一点是,所有的 Key 都可以共享同一套查找表。

从根本上说,查找表映射 Key / A 的任何计算的余数。我们对余数感兴趣,因为当余数 = 0 时,我们已经完成了,因为 A 已经是一个整数。

我建议我们有足够的哈希表来确保我们可以提前扫描而不必计算实际的余数。假设我们从 1 万亿开始,但这显然可以根据我们拥有多少计算能力而改变。

任何适当接近的 A/b 比率的哈希表如下。该表使用适当的余数进行索引(键控),并且任何给定余数处的值是可以沿 A * B 曲线遍历的“安全”距离,而余数不接触零。

您可以想象余数在 0 和 1 之间振荡(伪随机)。

该算法沿曲线选择数字 A,然后查找安全距离并跳转到下一个哈希表,或者至少该算法会进行这些因素检查,直到下一个哈希表可用为止。给定足够多的哈希表,我认为我们几乎可以避免大部分检查。

关于查找表的注释。

对于任何键,您都可以生成一个适合 A/B 比率的曲线表 重用表是必要的。建议的方法 从 N 的平方根(适当的键)生成 A/B 的一系列控制曲线,并在中途进行平方。假设每个比前一个键大 0.0001% 让我们也让表的大小说 A/B 比率的 1% 在计算互质因子时,选择与键匹配的最接近的查找表。选择您进入哈希表的入口点。这意味着记住表中的入口点与您的实际入口点的偏移量。查找表应该为入口点提供一系列点,对于这些点,对应的互质入口可能非常接近于零,需要手动检查。对于系列中的每个点,使用适当的数学公式计算实际偏移量。(这将是一个积分计算,我们需要一个数学家来看看它)为什么?因为我们的控制表是在 A/B 是 Key 的平方根时计算的。当我们沿着曲线移动时,我们需要适当地间隔开。作为奖励,数学家能否将 Key 空间折叠成 A/B 曲线上的一个点。如果是这样,我们只需要生成一个表。

关键概念


数字 A x B = Key 绘制以下内容:

X 轴映射 A 和 Y 轴映射 B。

曲线与 A 轴和 B 轴的接近程度取决于公钥的大小(其中 A x B = 密钥)。基本上,随着 Key 变大,曲线将向右移动。

现在我想让你消化或有疑问的想法是

  • 给定曲线上的任何点,都存在一个切线(A/B 之比)
  • 我们对 B 的值感兴趣,因为 A 在整数增量中增加并且本身就是一个整数。特别是,当 Key / A 余数为零时,我们真的只对 B 的余数感兴趣。我们将找到这个公钥的因素。具体来说,它将是我们尝试的 A 的最后一个值(也始终是整数),以及余数为零的值 B(整数也是如此)。
  • 基本算法很简单。-1- 在曲线上选择 A 为整数的点 -2- 找到 B 的余数,其中 Key/A 为 B -3- 检查 B 的余数是否为零,(如果为零,那么我们就完成了。 ) -4- 返回第 1 步,(接下来您将为 A 选择下一个整数)

这会起作用,但是太慢了。我们使用 HAL 算法所做的是改进上面的基本算法,以便我们可以跳过曲线的块,我们知道余数不会太接近零。

我们跳得越多,算法的效率就越高。

在我们进入改进的 HAL 算法之前,让我们回顾一个关键概念。

  • 对于非常大的 Key 值(请记住 A x B = Key),A/B 的比率几乎是恒定的,RSA 密钥是 2 次方 4096,这很大。

  • 假设我们已经创建了一组已经预加载到云中的表,这些表针对特定(大致)大小的键进行了优化。

    • 假设我们有 100 万个表仅用于这个特别窄的键大小范围
    • 每个表映射的切线或 A/B 比率略有不同,但请记住,所有这些表只能用于适当的键大小
    • 这些表格沿曲线均匀分布,因此对于我选择的任何点,都有一张表格可以告诉我在可能出现之前我可以安全地跳过多少个整数 A Key/A = B。请记住,我们不想错过 B 为零的点,否则 HAL 将无法工作。
    • 这些表使用当前剩余索引。(程序员或开发人员注意到这些查找表可以用 Hashtable 来实现,比如在 C# 或 Java 中)假设我们必须检查 A 沿曲线移动的所有点,每次都产生余数 B。只要 B 是足够接近任何索引,然后您可以使用该表计算出当 B 的余数为零时,您可以安全地跳过多少个整数而不会丢失。
  • 这件作品是一个批判性的概念。

    • 用一些合理的偏移量索引的每组查找表仅适用于特定的 Key 大小。
    • 随着一系列表的键值增大或缩小,查找的结果会“失焦”或变得更加不准确。
    • 因此,随着 Key 大小的增长,我们还需要创建一系列新的表。也许我们需要每增加 0.001% 的键就创建表。
于 2021-03-24T04:14:29.847 回答