Вычисление квадратного корня с алгоритмом сдвига битов всегда выдает одно и то же число - PullRequest
Новая
       17

Вычисление квадратного корня с алгоритмом сдвига битов всегда выдает одно и то же число

1 голос
/ 08 апреля 2019

Я борюсь с алгоритмом сдвига битов для вычисления квадратного корня больших чисел.У меня есть массивы 32-битных слов, и не имеет значения вход, выход всегда одно и то же число.Ранее алгоритм работал с 1 битом на ячейку массива, но когда я переключился на слова в ячейках, он больше не работает.
Я написал методы, которые прекрасно работают отдельно (добавление слов, вычитание слов, сдвиг битов вправо), новся программа не дает того, что я ожидаю.
Когда входное число имеет 0 в первой позиции, выходное значение равно 0, когда оно имеет любое число, но 1-я ячейка массива не равна 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};

Код:

one [0] = 1L << 30; </p> 

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;
}

Я не могу обнаружить ошибку в коде, особенно что всеметоды, кажется, работают, когда я проверяю их отдельно.

1 Ответ

0 голосов
/ 08 апреля 2019

isBigger не работает. Если у вас есть (длина 2) значения {2, 5} для a и {6, 3} для b, он вернет true, когда должен вернуть false. Внутри цикла вы хотите вернуть false, если 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. Однако эта функция довольно неэффективна. Его можно переписать так, чтобы ему требовался только один цикл и не было выделено памяти, но это оставлено для читателя в качестве упражнения.

...