使用位移算法计算平方根总是输出相同的数字

Question

我正在努力使用位移算法来计算大数的平方根。我有32位字的数组并且与输入无关，输出总是相同的数字。以前，该算法每个阵列单元使用1位，但当我切换到单元格中的单词时，它不再起作用。 我编写的方法分别完美地工作（添加单词，减去单词，向右移位）但整个程序没有给出我期望的结果。 当输入数字在其第一个位置为0时，输出为0，当它有任何数字但数组的第一个单元格不为0时，输出始终相同。

变量：

uint32_t var[4] = {0,0,0,0};
uint32_t w_number[word_len] = {1, 0,0,234324};
uint32_t one[word_len]      = {0,0,0,0};
uint32_t var[word_len]      = {0,0,0,0};
uint32_t buff[word_len]     = {0,0,0,0};
uint32_t result[word_len]   = {0,0,0,0};

代码：

一[0] = 1L << 30;

while (isBigger(one, input))
{
    shiftR_word(one);
    shiftR_word(one);
}

while (!isZero(one))
{
    add_word(result, one, var); //the result of one+result is put in Var. 

    if ((isBigger(input, var) || equals(input, var))) // if (input >= var) 
    {       
        subtract_word(input, var, input); // input-=var
        shiftR_word(result);
        add_word(result, one, result);          
    }
    else
    {
        shiftR_word(result);            
    }
    shiftR_word(one);
    shiftR_word(one);
}

std::cout << "\nOut: ";
printAsBit(result);
std::cout << std::endl;

这是我正在使用的可能导致问题的移位算法。

    void shiftR_word(uint32_t w_number[], int n=4)
    {
      // n - how many words
      //(n*32b word) >> 1
      bool* odd = new bool[n];

        for (int i = 0; i < n; i++)
        {
          if( w_number[i] & 1 )
            odd[i]=true;
          else
            odd[i]=false;
        }


        for (int i = 0; i < n; i++)
          w_number[i] >>= 1;

        for (int i = 0; i <= n-1; i++)
        {
          if(odd[i])
          {
            w_number[i+1] = w_number[i+1] | 1 << 31;
          }
        }

      delete[] odd;
    }

添加功能：

void add_word(uint32_t a[], uint32_t b[], uint32_t result[], int len=4)
{
  int carry=0;

  for (int i = len-1; i >=0; i--)
  {
    result[i]=a[i]+b[i]+carry;
    carry = (a[i]>result[i] || b[i]>result[i]) ? 1 : 0;

  } 
}

isBigger方法：

bool isBigger(uint32_t a[],uint32_t b[] ,int len=4)
{
    for (int i = 0; i < len; i++)
    {
      if (a[i]>b[i])
      {
        return true;
      }
    }
    return false;
}

我无法发现代码中的错误，特别是当我单独测试它们时，所有方法似乎都有效。

Answer 1

isBigger不起作用。如果a的（长度2）值为{2,5}，b的值为{6,3}，则返回false时将返回true。在循环内部，如果a[i] < b[i]，则要返回false，如果两个值相等，则仅检查下一个值。

bool isBigger(const uint32_t a[], const uint32_t b[], int len = 4)
{
    for (int i = 0; i < len; i++)
    {
      if (a[i] > b[i])
        return true;
      if (a[i] < b[i])
          return false;
    }
    // Only get here if `a` and `b` are equal
    return false;
}

此外，shiftR_word具有未定义的行为，因为w_number[i+1]可以超过数组的末尾（当i == n-1时，您将访问w_number[n - 1 + 1]或w_number[n]）。在这种情况下你的循环条件应该是i < n-1。但是，该功能效率很低。它可以被重写为只需要一个循环而不需要内存分配，但这仍然是读者的练习。