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

Как доделать длинную целочисленную арифметику? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти 100 первых простых чисел http://www.cyberforum.ru/cpp-beginners/thread751004.html
найти 100 первых простых чисел
C++ Оператор while Поскольку я еще начинающий, то задам такой вопрос: В цикл while мне нужно поставить несколько условий, вот, что я пишу: while (a1 = a2; a1 = a3; a1 = a4; a1 = a5; a1 = a6; a1 = a7; a1 = a8; a1 =... http://www.cyberforum.ru/cpp-beginners/thread751001.html
C++ По результату определить загаданное число
Клоун предложил каждому из публики задумать число. Потом он сказал: «Прибавьте к задуманному числу 5. Теперь из результата вычтите 2. А теперь к результату прибавьте 7». Потом клоун спросил у...
C++ Возврат массива из функции
Есть задача: используя функции, вычислить количество элементов заранее введённых массивов, которые кратны Х, и переписать в отдельный массив индексы отрицательных элементов этих массивов. Вот код: ...
C++ Определить наименьшее общее кратное двух натуральных чисел http://www.cyberforum.ru/cpp-beginners/thread750958.html
вот мой код. выдаёт одну ошибку. помогите пожалуйста найти. #include<iostream.h> main(int nok) { int a, b, nod, nok; cout<<"Vvedite chislo a"; cin>>a; cout<<"Vvedite chislo b";
C++ Нужно написать обход шахматной доски конем. На одну позицию можно стать один раз. Обеспечить алгоритм бектрекингу Добрый вечер! очень прошу помогите реализовать программу на с \ с + +. подробнее

Показать сообщение отдельно
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.01.2013, 12:57
Цитата Сообщение от taras atavin Посмотреть сообщение
И нужен ли здесь вообще вывод в поток, или он полезен только в тесте?
Надо ли делать ввод такого числа из потока и как сделать его десятичный ввод из потока?
Естественно. Значения не только вычисляются, но и вводятся-выводятся иногда. Как сделать — писать ограниченную реализацию десятичной длинной арифметики. Преобразование двоичного числа в десятичные циферки: поделить на 100, посмотреть остаток, записать остаток как следующие две цифры, поделить на 100... и так далее до нуля. И наоборот: разрезать длинное десятичное число на группы по две цифры, а потом много умножений этих байтиков на 100 в n-й степени и сложений. Сотня, потому что это наибольшая степень десяти, влезающая в байт. Представляли бы "цифры" как int32_t — это был бы миллиард.

Всё это можно ускорить divide-and-conquer-методом. И умножения на степени десяти превратить в сдвиги-сложения. И на ассемблере переписать, используя родные слова процессора, а не байты...

Цитата Сообщение от taras atavin Посмотреть сообщение
Меньше всего понимаю, как без временного буфера для результата сделать /= и *=.
Никак. Каждый байтик обрабатывается несколько раз в разные промежутки времени и влияет не только на себя и максимум одного соседа, как это при сложении-вычитании, так что вам потребуется полный буфер, а не один байтик.

Добавлено через 29 минут
Чтоб уж точно понятно было, как переводить системы туда-сюда.

Ну вот вы представлете число 152365126310. Режем его на кусочки по две цифры (с конца, отсюда и далее все циферки без указания системы записаны в шестнадцатеричной):
0F 17 41 0C 3F
Объединяем байтики в пары (например, 0C | 3F → 0C * 10010 + 3F = 04EF):
000F 093D 04EF
Затем пары в четвёрки:
0000000F 0168E3BF
Затем, наконец, всё это в одну восьмёрку:
000000005AD112BF
Так уж вышло, что в младшей четвёрке старшие разряды были пустые и всё влезло в одну четвёрку. Итого мы получили своё 5AD112BF16 = 152365126310.

Точно так же преобразуется наборот. Надо разделить 5AD112BF на два примерно одинаковых множителя делением на степень десятки. Потом то, что получится, ещё раз, и так далее, пока не получим байтики, в которых по две десятичные цифры. Берём нашу сотню и начинаем возводить её в квадрат, пока не перелетим за 5AD112BF: 64, 2710, 5F5E100, приехали. Делим 5AD112BF на 5F5E100, получаем частное F и остаток 168E3BF. F — это цифры после восьми младших, 168E3BF — младшие восемь десятичных цифр. Делим 168E3BF на 2710, получаем частное 93D и остаток 4EF. Наконец, каждое из них делим на 64 и получаем свою кучку пар десятичных циферок:
0F 17 41 0C 3F
Которые уже склеиваем в строку из десятичных циферок по вкусу.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru