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

Возведение в степень - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.65
v0l0d1ka
9 / 9 / 0
Регистрация: 14.12.2010
Сообщений: 127
09.10.2011, 01:28     Возведение в степень #1
Подскажите, как написать программу возведения 2-ки в миллионную степень и вывести результат на экран.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <math.h>
#include <cstdlib>
 
 
int main ()
{
  printf ("7 ^ 3 = %lf\n", pow (7.0,3.0));
  printf ("4.73 ^ 12 = %lf\n", pow (4.73,12.0));
  printf ("32.01 ^ 1.54 = %lf\n", pow (32.01,1.54));
  printf ("2 ^ 1000000.0 = %lf\n", pow (2.0,1000000.0));
  system("pause");
  return 0;
}
Не работает.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2011, 01:28     Возведение в степень
Посмотрите здесь:

C++ Возведение в степень!
возведение в степень C++
C++ Возведение степень
C++ Возведение в степень
Возведение в степень C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
09.10.2011, 01:33     Возведение в степень #2
v0l0d1ka, вы представляете себе агрегат, который в состоянии вычислить
C
1
printf ("2 ^ 1000000.0 = %lf\n", pow (2.0,1000000.0))
это 1000000 / 4 ядер процессора intel x32 плюс еще парочка чтобы вся эта параллель функционировала.
v0l0d1ka
9 / 9 / 0
Регистрация: 14.12.2010
Сообщений: 127
09.10.2011, 01:47  [ТС]     Возведение в степень #3
т.е. на одной обычной машине эта программа будет работать очень долго?
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 02:00     Возведение в степень #4
Такое большое число как 2 в степени 1 млн не влезет в стандартные типы и значит использовать функцию pow нельзя
Нужен или собственный класс больших чисел - но это вряд ли хороший подход, если нужно только двойку рассматривать
Или посмотреть что-то насчет представления степеней двойки, например в двоичном виде 2 в степени 1 млн запишется как 10.......0 - миллион нулей после единицы
А еще можно заметить закономерности построения степеней двойки, например они заканчиваются на 2, 4, 8, 6 всегда и эти цифры повторяются в указанном порядке))
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
09.10.2011, 02:04     Возведение в степень #5
ну простая арифметика показывает, что число будет
2 ^ 10e6 = (2^10) ^ 10e5 ~ 10e3 ^ 100000 = 10e300000 ну довольно много
тем не менее есть более менее быстрые алгоритмы возведения в степень, идея такая, несложно распространить на миллион
2^30 = 4^15 = 8^14 = 64^7 = 128^6 = 16384^3 = 32768^2 = 1073741824
получится всего лишь порядка полумиллиона операций умножения и деления
конечно вопрос в том как промежуточные вычисления да и результа в 300000 знаков хранить
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
09.10.2011, 02:05     Возведение в степень #6
Цитата Сообщение от v0l0d1ka Посмотреть сообщение
т.е. на одной обычной машине эта программа будет работать очень долго?
в предыдущем посте я преувеличил конечно, все немного проще... но сути не меняет. максимальную разрядность можно вычислить так
C
1
sizeof(long double) * 8;
это и будет максимальная степень без применения методов длинной арифметики.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
09.10.2011, 02:15     Возведение в степень #7
не, я кстати соврал там для получения степени числа надо порядка 20-30 умножений
но хранить результат все равно както нужно
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 03:29     Возведение в степень #8
Написала программку, решающую задачу "в лоб", т.е. она действительно возводит 2 в степень 100 000 путем перемножения 2*2*2... Естественно, работает ОЧЕНЬ долго) При возведении в степень 1 млн вообще можно будет состариться)
Числа хранятся в виде массивов
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
#include <iostream>
using namespace std;
 
void print(int* a, int N)
{
    for(int i=0;i<N;i++)
        cout<<a[i];
    cout<<endl;
}
 
int main()
{
    int Na=1,Nb;
    int *a;
    int *b;
    a=new int[Na];
    a[0]=2;//стартуем с 2-ки
    int perenos=0;
    int j=1;
    while(j<100000)
    {
        Nb=Na;
        if(a[0]>4)
        {
                Nb++;
        }
        b=new int[Nb];
        //b[0]=0;
        perenos=0;
        for(int i=Na-1;i>=0;i--)
        {
            b[i+Nb-Na]=(a[i]*2)%10;
                if(perenos) b[i+Nb-Na]+=perenos;
            perenos=(a[i]*2)/10;
        }
        if(Nb>Na) 
            b[0]=perenos;
        if(Nb>Na)
        {
            delete []a;
            a=new int [Nb];
        }
        Na=Nb;
        for(int i=0;i<Na;i++)
            a[i]=b[i];
        delete []b;
        j++;
    }
    print(a,Na);
    delete[]a;
}
Завтра попытаюсь реализовать алгоритм быстрого возведения в степень
Если есть какие-то мысли по оптимизации хранения числа. буду рада услышать
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
09.10.2011, 04:27     Возведение в степень #9
а может кто знает реально ли в обход стандарта оперировать в Си деками по пол байта?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 07:53     Возведение в степень #10
На яве у меня полминуты считает.
Ну там бинарное возведение в степень используется, оно за O(log n) работает.
На плюсах можно быстрее.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.10.2011, 08:18     Возведение в степень #11
Цитата Сообщение от alkagolik Посмотреть сообщение
реально ли в обход стандарта оперировать в Си деками по пол байта?
Кроме логических операций есть несколько интристик (не знаю, как их по человечески назвать), которые для студии заточены. Циклические сдвиги и т.п., чего в Си нет они реализуют.
А вообще я вопрос не понял.)
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
09.10.2011, 09:25     Возведение в степень #12
Цитата Сообщение от diagon Посмотреть сообщение
На яве у меня полминуты считает
haskell считает чуть больше секунды

Добавлено через 32 минуты
Цитата Сообщение от Nameless One Посмотреть сообщение
haskell считает чуть больше секунды
даже меньше, 0.3 секунды
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 13:46     Возведение в степень #13
Так я ж и не претендую на самый оптимальный вариант решения задачи) Я ж сказала, что решаю "в лоб"
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения?
Как будут силы, напишу бинарное возведение в степень, это ускорит работу. Еще наверное надо подумать над оптимизацией хранения числа
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 13:49     Возведение в степень #14
Цитата Сообщение от aeshes Посмотреть сообщение
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения?
Да все также "в лоб"
Java
1
2
3
4
5
6
7
8
9
10
import java.math.BigInteger;
 
class Main
{
    public static void main( String[] args )
    {
        System.out.println( BigInteger.valueOf(2).pow( 1000000 ) );
    }
 
}
Или так(секунд за 10 считает):
Python
1
2 ** 1000000
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 13:52     Возведение в степень #15
ну так здесь используются надстройки для работы с большими числами, включенные в среду, как я поняла
А если без них? т.е. самостоятельно реализовать задачу - есть пример?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
09.10.2011, 13:53     Возведение в степень #16
Цитата Сообщение от aeshes Посмотреть сообщение
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения?
Код
[nameless@desktop haskell]$ cat sample.hs
import System.Environment (getArgs)

main = getArgs >>= print . (2^) . read . head
[nameless@desktop haskell]$ ghc --make sample.hs
[1 of 1] Compiling Main             ( sample.hs, sample.o )
Linking sample ...
[nameless@desktop haskell]$ time ./sample 1000000 > /dev/null

real	0m0.271s
user	0m0.267s
sys	0m0.001s
[nameless@desktop haskell]$
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 14:05     Возведение в степень #17
Nameless One, я наверное, себя переоценила, потому что в хаскеле ничего не поняла ))
Но мне кажется строчка
main = getArgs >>= print . (2^) . read . head
берет аргументы из командной строки и возводит в степень средствами языка? типа запись 2^1000000?
А мне хотелось увидеть именно сам алгоритм быстрого возведения
Поправьте, если ошиблась, просто программу на хаскеле вижу первый раз
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 14:12     Возведение в степень #18
Цитата Сообщение от aeshes Посмотреть сообщение
А мне хотелось увидеть именно сам алгоритм быстрого возведения
http://e-maxx.ru/algo/binary_pow
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
09.10.2011, 14:14     Возведение в степень #19
Цитата Сообщение от aeshes Посмотреть сообщение
берет аргументы из командной строки и возводит в степень средствами языка? типа запись 2^1000000?
берет список аргументов из командной строки, берет первый элемент из списка, переводит его в число и возводит двойку в эту степень

Цитата Сообщение от aeshes Посмотреть сообщение
А мне хотелось увидеть именно сам алгоритм быстрого возведения
так их в гугле полным-полно
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2011, 14:22     Возведение в степень
Еще ссылки по теме:

C++ Возведение в степень
C++ возведение в степень

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

Или воспользуйтесь поиском по форуму:
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 14:22     Возведение в степень #20
Я знаю этот алгоритм, сама его писала тоже в качестве тренировки, безотносительно к большим числам) Просто хотела посмотреть на его реализацию применительно к большим числам в разных форматах хранения/представления. Так понимаю, что от реализации математических операций над большими числами (ну хотя бы умножения) в конкретном представлении все равно не уйти. А когда будет умножение, можно уже и возведение в степень реализовать
Просто было подозрение, что помимо быстрого возведения в степень можно как-то оптимизировать способ хранения большого числа именно для этой задачи, где 2 в основании

Nameless One, Спасибо. Примерно так и поняла. Т.е., используются средства языка для работы с большими числами
Yandex
Объявления
09.10.2011, 14:22     Возведение в степень
Ответ Создать тему
Опции темы

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