Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.95/64: Рейтинг темы: голосов - 64, средняя оценка - 4.95
9 / 9 / 3
Регистрация: 14.12.2010
Сообщений: 129
1

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

09.10.2011, 01:28. Показов 12629. Ответов 30
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Подскажите, как написать программу возведения 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;
}
Не работает.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.10.2011, 01:28
Ответы с готовыми решениями:

Возведение в степень!
Возник вопрос - Возможно пока не понятна в чем мысль! Попробую на примере объяснить!...

возведение в степень!
Кто помнит функцию возведения в степень.?? &quot;трам-пам-пам&quot; (a,b) ???? Добавлено через 3 минуты...

Возведение в степень
Почему, когда я пытаюсь возвести в квадрат x с типом int, то получается 24, а когда с типом double,...

Возведение в степень
Подскажите оператор для возведения числа в n-ую степень. Зарание спасиба

30
Заблокирован
09.10.2011, 01:33 2
v0l0d1ka, вы представляете себе агрегат, который в состоянии вычислить
C
1
printf ("2 ^ 1000000.0 = %lf\n", pow (2.0,1000000.0))
это 1000000 / 4 ядер процессора intel x32 плюс еще парочка чтобы вся эта параллель функционировала.
0
9 / 9 / 3
Регистрация: 14.12.2010
Сообщений: 129
09.10.2011, 01:47  [ТС] 3
т.е. на одной обычной машине эта программа будет работать очень долго?
0
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 02:00 4
Такое большое число как 2 в степени 1 млн не влезет в стандартные типы и значит использовать функцию pow нельзя
Нужен или собственный класс больших чисел - но это вряд ли хороший подход, если нужно только двойку рассматривать
Или посмотреть что-то насчет представления степеней двойки, например в двоичном виде 2 в степени 1 млн запишется как 10.......0 - миллион нулей после единицы
А еще можно заметить закономерности построения степеней двойки, например они заканчиваются на 2, 4, 8, 6 всегда и эти цифры повторяются в указанном порядке))
0
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
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 знаков хранить
0
Заблокирован
09.10.2011, 02:05 6
Цитата Сообщение от v0l0d1ka Посмотреть сообщение
т.е. на одной обычной машине эта программа будет работать очень долго?
в предыдущем посте я преувеличил конечно, все немного проще... но сути не меняет. максимальную разрядность можно вычислить так
C
1
sizeof(long double) * 8;
это и будет максимальная степень без применения методов длинной арифметики.
0
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
09.10.2011, 02:15 7
не, я кстати соврал там для получения степени числа надо порядка 20-30 умножений
но хранить результат все равно както нужно
0
448 / 211 / 21
Регистрация: 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;
}
Завтра попытаюсь реализовать алгоритм быстрого возведения в степень
Если есть какие-то мысли по оптимизации хранения числа. буду рада услышать
0
Заблокирован
09.10.2011, 04:27 9
а может кто знает реально ли в обход стандарта оперировать в Си деками по пол байта?
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 07:53 10
На яве у меня полминуты считает.
Ну там бинарное возведение в степень используется, оно за O(log n) работает.
На плюсах можно быстрее.
0
Делаю внезапно и красиво
Эксперт С++
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
09.10.2011, 08:18 11
Цитата Сообщение от alkagolik Посмотреть сообщение
реально ли в обход стандарта оперировать в Си деками по пол байта?
Кроме логических операций есть несколько интристик (не знаю, как их по человечески назвать), которые для студии заточены. Циклические сдвиги и т.п., чего в Си нет они реализуют.
А вообще я вопрос не понял.)
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
09.10.2011, 09:25 12
Цитата Сообщение от diagon Посмотреть сообщение
На яве у меня полминуты считает
haskell считает чуть больше секунды

Добавлено через 32 минуты
Цитата Сообщение от Nameless One Посмотреть сообщение
haskell считает чуть больше секунды
даже меньше, 0.3 секунды
0
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 13:46 13
Так я ж и не претендую на самый оптимальный вариант решения задачи) Я ж сказала, что решаю "в лоб"
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения?
Как будут силы, напишу бинарное возведение в степень, это ускорит работу. Еще наверное надо подумать над оптимизацией хранения числа
0
Higher
1953 / 1219 / 120
Регистрация: 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
0
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 13:52 15
ну так здесь используются надстройки для работы с большими числами, включенные в среду, как я поняла
А если без них? т.е. самостоятельно реализовать задачу - есть пример?
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
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]$
0
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 14:05 17
Nameless One, я наверное, себя переоценила, потому что в хаскеле ничего не поняла ))
Но мне кажется строчка
main = getArgs >>= print . (2^) . read . head
берет аргументы из командной строки и возводит в степень средствами языка? типа запись 2^1000000?
А мне хотелось увидеть именно сам алгоритм быстрого возведения
Поправьте, если ошиблась, просто программу на хаскеле вижу первый раз
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 14:12 18
Цитата Сообщение от aeshes Посмотреть сообщение
А мне хотелось увидеть именно сам алгоритм быстрого возведения
http://e-maxx.ru/algo/binary_pow
1
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
09.10.2011, 14:14 19
Цитата Сообщение от aeshes Посмотреть сообщение
берет аргументы из командной строки и возводит в степень средствами языка? типа запись 2^1000000?
берет список аргументов из командной строки, берет первый элемент из списка, переводит его в число и возводит двойку в эту степень

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

Nameless One, Спасибо. Примерно так и поняла. Т.е., используются средства языка для работы с большими числами
0
09.10.2011, 14:22
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.10.2011, 14:22
Помогаю со студенческими работами здесь

Возведение в степень
подскажите,пожалуйста, способ реализации (алгоритм)операции возведение в степень числа с...

Возведение в степень
Здравствуйте, нужно возвести константу &quot;e&quot; в степень -x-2, может кто-нибудь подскажет как это...

Возведение в степень
Вам конечно это покажется тупой проблемой, но всё же. Напишите пожалуйста как возводить в степень...

возведение в степень
помогите плиз! в файле есть задачка. нужно рекурсивно возвести в степень. Код: #include &lt;iostream&gt;...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru