时间戳

首页 > 解决方案 > 用位移算法计算平方根总是输出相同的数字

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

问题描述

我正在为计算大数平方根的位移算法而苦苦挣扎。我有 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;
}

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

标签： c++algorithmsquare-root

解决方案

isBigger不起作用。如果您有 {2, 5} fora和 {6, 3} for的 (length 2) 值，b它将true在它应该返回 false 时返回。在循环内部，您希望返回 false if a[i] < b[i]，并且仅在两个值相等时才检查下一个值。

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. 但是，该功能相当低效。它可以被重写为只需要一个循环并且不需要内存分配，但这留给读者作为练习。

推荐阅读