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

Извлечение корня, длинная арифметика - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.10.2011, 13:58     Извлечение корня, длинная арифметика #1
По заданному натуральному числу А требуется найти наибольшее число В такое, что B^2 <= A.

вот набросал, но прога работает медленно. как ее можно оптимизировать или подскажите более быстрый способ.
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <fstream>
#include <string>
#include <deque>
using namespace std;
 
int sravnenie(deque<int>& a,deque<int>& b)
{   
    int lena=a.size(),lenb=b.size();
    if (lena>lenb) return 1;
    if (lena<lenb) return 2;
    if (lena==lenb)
    {
        for (int i=0;i<lena;i++)
        {
            if (a[i]!=b[i])
                if (a[i]>b[i]) 
                    return 1;
                else
                    return 2;
        }
    }
    return 0;
}
 
 
deque<int> slozhenie(deque<int>& a,deque<int>& b)
{  
    if (a.empty()) 
        return b;
    else
    {
        int lena=a.size()-1,lenb=b.size()-1;
        int perenos = 0, achislo, bchislo, summa, i=0;
        deque<int> res;
        do 
        {
            if (lena>=i)
                achislo = a[lena-i];
            else
                achislo = 0;
 
            if (lenb >= i) 
                bchislo = b[lenb-i];
            else
                bchislo = 0;
 
            summa = achislo + bchislo + perenos;
            if (summa >= 10 )
            {
                perenos = summa / 10;
                summa = summa % 10;
            }
            else
            {perenos = 0;}
 
            res.push_front(summa);
            i++;
        }while((lena>=i)||(lenb>=i));
 
        if (perenos > 0)
        {
            res.push_front( perenos);
        }
        return res;
    }
}
 
deque <int> sq2(deque<int>& y)
{
    deque <int> a=y;
    int h=0;
    while( (!a.empty()) && (!a.back()))  {a.pop_back(); h++;}   
 
    int perenos,proizvedenie;
    int lena=a.size()-1;
    deque<int> proizv,res;
    for(int i = lena; i>=0; i--)
    {
        proizv.clear(); 
        perenos = 0;       
 
        for (int j = lena; j>=0; j--)
        {       
            proizvedenie = a[i] * a[j] + perenos;
 
            if (proizvedenie >= 10) 
            {
                perenos = proizvedenie / 10;
                proizvedenie %= 10;
            }
            else
            {perenos = 0;}          
 
            proizv.push_front(proizvedenie);
        }
        if (perenos > 0) {proizv.push_front(perenos);}
        while( (!proizv.empty()) && (!proizv.front()))  {proizv.pop_front();}
        proizv.resize(proizv.size()+lena-i);
        res=slozhenie(res,proizv);
    }    
 
    res.resize(res.size()+2*h);
    return res;
}
 
deque<int> sqrt(deque<int>& a)
{
    int n=(a.size()+1)/2;
    deque<int> r(n);
 
    for(int i=0;i<n;i++)
    {
        for (int j=9;j>=0;j--)
        {
            r[i]=j;
            if (sravnenie(sq2(r),a)!=1) break;
        }
    }
    return r;       
}
 
int main(void)
{   
    string in;
    ifstream fin ("INPUT.TXT"); 
    ofstream fout ("OUTPUT.TXT");
    fin >> in;
    deque<int> a;
    for (unsigned int i=0;i<in.size();i++)  a.push_back(in[i]-48);
    deque<int> rezult=sqrt(a);
    for (unsigned int i=0;i<rezult.size();i++)  fout <<rezult[i];
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2011, 13:58     Извлечение корня, длинная арифметика
Посмотрите здесь:

C++ Длинная арифметика
C++ Длинная арифметика))
Длинная арифметика C++
C++ Длинная арифметика
C++ длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hepr
 Аватар для hepr
60 / 32 / 5
Регистрация: 21.10.2010
Сообщений: 538
08.10.2011, 15:25     Извлечение корня, длинная арифметика #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
#include "stdafx.h"
#include "iostream"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int a;
    cin >> a;
    unsigned int first,second;
    first = second = 0;
    for (register unsigned int b=1;;b++)
    {
        second = b*b;
        if(second<=a)
            first = b;
        else
        {
            cout << first;
            break;
        }
    }
    system("pause");
    return 0;
}
Добавлено через 38 секунд
Если я конечно правильно понял задание
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.10.2011, 15:34  [ТС]     Извлечение корня, длинная арифметика #3
для чисел до 10^3000
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
08.10.2011, 15:37     Извлечение корня, длинная арифметика #4
C++
1
b = static_cast<int>(sqrt(static_cast<double>(a)));
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.10.2011, 17:11  [ТС]     Извлечение корня, длинная арифметика #5
Цитата Сообщение от kazak Посмотреть сообщение
C++
1
b = static_cast<int>(sqrt(static_cast<double>(a)));
и как с помощью этого извлечете целую часть корня например из 100 значного целого числа?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.10.2011, 17:20     Извлечение корня, длинная арифметика #6
Было решение на e-maxx.ru, но почему-то не могу найти там эту тему, поэтому просто выложу исходник.
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <cstdlib>
#include <stdio.h>
#include <string.h>
 
using namespace std;
typedef unsigned char uchar;
typedef unsigned short ushort;
 
#define MAX_LEN 3100
#define bigint ushort *
#define base 10
 
bigint tmp = new ushort[MAX_LEN];
bigint prr = new ushort[MAX_LEN];
bigint tmp1 = new ushort[MAX_LEN];
bigint tmp2 = new ushort[MAX_LEN];
 
int cmp(bigint a, bigint b){
    if(a[0]!=b[0]) return (int)a[0]-b[0];
    for(register int i=a[0];i>0;i--)
        if(a[i]!=b[i]) return (int)a[i]-b[i];
    return 0;
}
 
bigint read(){
    bigint r = new ushort[MAX_LEN];
    char s[MAX_LEN];
    scanf("%s",s);
    int c = 0, l = strlen(s);
    if(l>1)
        for(int i=0;i<l;i++, c++)
            if(s[i]!='0') break;
    r[0]=l-c;
    for(register int i=l-1; i>=c; i--)
        r[l-i]=s[i]-'0';
    return r;
}
 
void write(bigint n){
    for(int i=n[0];i>0;i--)
        printf("%d",n[i]);
}
 
void smul(bigint a, ushort b, bigint c) {
    long i, temp;
    ushort carry=0; 
    for (i=1; i<=a[0];i++) {
        temp = a[i]*b + carry;
        carry = temp / base;
        c[i] = temp - carry*base;
    }
    if (carry) {
        c[i] = carry;
        c[0] = a[0]+1;
    } 
    else c[0] = a[0];
    while(c[0]>0 && c[c[0]]==0) c[0]--;
}
 
void shift(bigint a, int s){
    for(int i=a[0];i>0;i--)
        a[i+s] = a[i];
    for(int i=1;i<=s;i++) a[i]=0;
    a[0]+=s;
}
 
void summ(bigint a, bigint b, bigint c){
    long i, temp;
    ushort carry = 0;
    if ( a[0] < b[0] ) {
        summ(b,a,c);
        return;
    }
    for (i=1; i<=b[0]; i++) {
        temp = a[i] + b[i] + carry;
        if (temp >= base) {
            c[i] = temp - base;
            carry = 1;
        } else {
            c[i] = temp;
            carry = 0;
        }
    }
    for (; i <= a[0]; i++) {
        temp = a[i] + carry;
        if (temp >= base) {
            c[i] = temp - base;
            carry = 1;
        } else {
            c[i] = temp;
            carry = 0;
        }
    }
    if (carry) {
        c[i] = carry;
        c[0] = a[0]+1;
    } 
    else c[0] = a[0];
    while(c[0]>0 && c[c[0]]==0) c[0]--;
}
 
ushort findBin(bigint a, bigint r, int cur){
    // though... it's not a binary search.
    short res = base-1;
    ushort up = base-1, down = 0;
    while(res>0){
        smul(r, 2, tmp1);
        smul(tmp1, res, tmp2);
        shift(tmp2, cur-1);
        summ(prr, tmp2, tmp);
        tmp1[0]=1; tmp1[1]=res;
        smul(tmp1, res, tmp2);
        shift(tmp2, cur*2-2);
        summ(tmp, tmp2, tmp1);
        if(cmp(tmp1,a)<=0){ 
            break;
        }
        res--;
    }
    while(res>=base) res--;
    smul(r, 2, tmp1);
    smul(tmp1, res, tmp2);
    shift(tmp2, cur-1);
    summ(prr, tmp2, tmp);
    tmp1[0]=1; tmp1[1]=res;
    smul(tmp1, res, tmp2);
    shift(tmp2, cur*2-2);
    summ(tmp, tmp2, prr); 
    return r[cur]=res;
}
 
bigint sqrt(bigint a){
    bigint r = new ushort[MAX_LEN];
    r[0] = (a[0]+1)>>1;
    for(register int i=1;i<=r[0];i++)
        r[i]=0;
    register int cur = r[0];
    while(cur){
        r[0] = (a[0]+1)>>1;
        r[cur]=findBin(a, r, cur);
        cur--;
    }
    return r;
}
 
// Program entry
int main(int argc, char** argv) {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    bigint n; bigint s;
    prr[0]=0;
    n = read();
    s = sqrt(n);
    write(s);
    return 0;
}
Yandex
Объявления
08.10.2011, 17:20     Извлечение корня, длинная арифметика
Ответ Создать тему
Опции темы

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