Форум программистов, компьютерный форум CyberForum.ru

Длинная арифметика. Сложение - C++

Восстановить пароль Регистрация
 
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
07.03.2014, 23:52     Длинная арифметика. Сложение #1
Есть класс BigInt со скрытыми переменными uint32* m_integer и uint32 m_length, которые отвечают за само число и его длину соответственно. Я реализовал оператор +. Укажите, пожалуйста, на ошибки в реализации (кроме <cstring>) -- как можно было сделать лучше (быстрее)?
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
BigInt BigInt::operator+(const BigInt& rhs) const
{
    if (m_length == 0 || rhs.m_length == 0)
        throw "Empty number in BigInt::operator+";
    
    BigInt result;
 
    if (m_length == rhs.m_length)
    {       
        result.m_integer = new uint32[m_length + 1];
        result.m_length = m_length + 1;
        memset(result.m_integer, 0x0, (m_length + 1) * sizeof(uint32));
 
        for (uint32 i = 0; i < m_length; ++i)
        {
            result.m_integer[i] += m_integer[i] + rhs.m_integer[i];
            if (result.m_integer[i] < m_integer[i])
                ++result.m_integer[i + 1];
        }
 
        return result;
    }
 
    if (m_length > rhs.m_length)
    {
        result.m_integer = new uint32[m_length + 1];
        result.m_length = m_length + 1;
        memset(result.m_integer, 0x0, (m_length + 1) * sizeof(uint32));
 
        for (uint32 i = 0; i < rhs.m_length; ++i)
        {
            result.m_integer[i] += m_integer[i] + rhs.m_integer[i];
            if (result.m_integer[i] < m_integer[i])
                ++result.m_integer[i + 1];
        }
 
        for (uint32 i = rhs.m_length; i < m_length; ++i)
        {
            if (result.m_integer[i] == 0)
            {
                memcpy(&result.m_integer[i], &m_integer[i], (m_length - i) * sizeof(uint32));
                break;
            }
            else
            {
                result.m_integer[i] = m_integer[i] + 1;
                if (result.m_integer[i] == 0)
                    ++result.m_integer[i + 1];
            }
        }
    }
    else
    {
        result.m_integer = new uint32[rhs.m_length + 1];
        result.m_length = rhs.m_length + 1;
        memset(result.m_integer, 0x0, (rhs.m_length + 1) * sizeof(uint32));
 
        for (uint32 i = 0; i < m_length; ++i)
        {
            result.m_integer[i] += m_integer[i] + rhs.m_integer[i];
            if (result.m_integer[i] < m_integer[i])
                ++result.m_integer[i + 1];
        }
 
        for (uint32 i = m_length; i < rhs.m_length; ++i)
        {
            if (result.m_integer[i] == 0)
            {
                memcpy(&result.m_integer[i], &rhs.m_integer[i], (rhs.m_length - i) * sizeof(uint32));
                break;
            }               
            else
            {
                result.m_integer[i] = rhs.m_integer[i] + 1;
                if (result.m_integer[i] == 0)
                    ++result.m_integer[i + 1];
            }
        }
    }
    
    return result;
}

Заранее благодарен!

Добавлено через 4 часа 48 минут
Гляньте за одно ещё и квадрат, пожалуйста! Почти уверен, что можно сделать ещё быстрее
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
BigInt BigInt::operator*(const BigInt& rhs) const
{
    if (m_length == 0 || rhs.m_length == 0)
        throw "Empty number in BigInt::operator*";
 
    BigInt result;
 
    result.m_integer = new uint32[m_length + rhs.m_length];
    result.m_length = m_length + rhs.m_length;
    memset(result.m_integer, 0x0, (m_length + rhs.m_length) * sizeof(uint32));
 
    for (uint32 i = 0; i < m_length; ++i)
    {
        uint32 carry = 0;
 
        for (uint32 j = 0; j < rhs.m_length; ++j)
        {
            uint64 temp = ((uint64)m_integer[i] * rhs.m_integer[j]) + result.m_integer[i + j] + carry;
            result.m_integer[i + j] = (uint32)temp;
            carry = (uint32)(temp >> 32);
        }
 
        result.m_integer[i + rhs.m_length] = carry;
    }
 
    return result;
}
 
BigInt BigInt::sqr() const
{
    if (m_length == 0)
        throw "Empty number in BigInt::sqr";
 
    BigInt result;
 
    result.m_integer = new uint32[m_length << 1];
    result.m_length = m_length << 1;
    memset(result.m_integer, 0x0, (m_length << 1) * sizeof(uint32));
 
    // cross-products
    for (uint32 shift = 1; shift < m_length; ++shift)
    {
        uint32 carry = 0;
 
        for (uint32 i = 0; i < (m_length - shift); ++i)
        {
            uint64 temp = ((uint64)m_integer[i] * m_integer[i + shift]) + result.m_integer[shift + (i << 1)] + carry;
            result.m_integer[shift + (i << 1)] = (uint32)temp;
 
            temp >>= 32;
            result.m_integer[shift + (i << 1) + 1] += temp;
            if (result.m_integer[shift + (i << 1) + 1] < temp)
                carry = 1;
            else
                carry = 0;
        }
    }
 
    // shift
    for (uint32 i = result.m_length - 1; i > 0; --i)
    {
        result.m_integer[i] <<= 1;
        result.m_integer[i] |= result.m_integer[i - 1] >> 31;
    }
 
    // squares
    uint32 carry = 0;
    for (uint32 i = 0; i < m_length; ++i)
    {
        uint64 temp = ((uint64)m_integer[i] * m_integer[i]) + result.m_integer[i << 1] + carry;
        result.m_integer[i << 1] = (uint32)temp;
 
        temp >>= 32;
        result.m_integer[(i << 1) + 1] += temp;
        if (result.m_integer[(i << 1) + 1] < temp)
            carry = 1;
        else
            carry = 0;
    }
 
    return result;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2014, 23:52     Длинная арифметика. Сложение
Посмотрите здесь:

C++ Длинная арифметика
C++ Длинная арифметика))
Длинная арифметика C++
C++ Длинная арифметика
Длинная арифметика C++
длинная арифметика C++
C++ Сложение больших чисел (длинная арифметика)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
08.03.2014, 00:34     Длинная арифметика. Сложение #2
не знаю насчет быстрее но меньше кода это точно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
BigInt BigInt::operator+(const BigInt& rhs) const
{
  if (!(m_length*rhs.m_length ))
        throw "Empty number in BigInt::operator+";
  BigInt result;
   BigInt *tmp,*tmp1;
  if (m_length<rhs.m_length)
    {
     tmp=&rhs
     tmp1=this;
    }
    else
    {
     tmp1=&rhs
     tmp=this ;
    }
   result.m_integer = new uint32[tmp->m_length ];
   result.m_length = tmp->m_length ;
   memset(result.m_integer, 0x0, (tmp->m_length ) * sizeof(uint32));
   memcpy(result.m_integer, tmp->m_integer,(m_length ) * sizeof(uint32));
 bool flag=false;  
 for (uint32 i = 0; i <tmp1-> m_length; ++i)
   {
     result.m_integer[i] +=tmp1->m_integer[i];
       if (result.m_integer[i] < tmp1->m_integer[i])
         {
           if( i < m_length-1 && tmp-> m_length!=tmp1-> m_length )
             ++result.m_integer[i + 1];
           else
              flag= true;
          }
    } 
if(flag)
 {
  uint32 * addr1= new uint32[result.m_length +1];
   memcpy(addr,result.m_integer,(result.m_length +1) * sizeof(uint32));
  addr1[result.m_length++]=1;
  delete [] result.m_integer;
  result.m_integer=addr1; 
  }
 return result;
}
писал прямо здесь
проверь на ошибки
но идея надеюсь понятна
выделяем памяти под больший размер ( если одинаковы то без разницы)
потом копируем в результат большее число
потом в цикле прибавляем меньшее
если на последней итерации переполнение и размеры равны
то перераспределяем память ( увеличиваем на 1)
копируем значение а в старший разряд записываем 1

Добавлено через 1 минуту
Цитата Сообщение от vlad_light Посмотреть сообщение
if (m_length == rhs.m_length)
* * { * * *
* * * * result.m_integer = new uint32[m_length + 1];
вот здесь у тебя косячек
если размеры равны но там записана 1
т.е в каждом размер m_length =1
то при сложении переполнения не будет
но памяти ты выделишь уже 2
Yandex
Объявления
08.03.2014, 00:34     Длинная арифметика. Сложение
Ответ Создать тему
Опции темы

Текущее время: 01:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru