Работа с большими числами

@mmos · Регистрация: 06.03.2011

Author24 — интернет-сервис помощи студентам

Писал-с!

Чертовски интересная задача. Делать надо всё с нуля.

Но ведь и овчинка выделки стоит. Не так ли?

30.04.2006, 00:42

Если писать самому и качественно, то с применением ассемблера и формата BCD (Binary Coded Decimals - Двоично Кодированные Десятичные).
BCD могут быть неупакованные - на каждую десятичную цифру приходится один байт; и упакованные - по 4 бита. Неупакованные BCD обрабатываются процессором по одной цифре за операцию. Кроме обычных комманд для сложения/вычитания есть специфичные для BCD комманды: aaa, aas, aad, aam, daa, das и др. Арифметический сопроцессор может за операцию обрабатывать 10-байтные упакованные BCD (это 18 цифр числа + знаковый байт)
Плюс неупакованные BCD легко переводятся в ASCII строку и наоборот.
Основы работы с BCD должны быть в любом нормальном учебнике по ассемблеру.
Удачи

@shurezz · 03.05.2006, 21:20

А чем Вам не нравится мой вариант с сохранением числа вида #.### и количества десятков отдельно? Объясните. Помоему и места мало и проще некуда.

С уважением, Александр.

05.05.2006, 13:48

Никто здесь не говорил, что это кому-то не нравится.
А вот мне лично не совсем понятна идея.
Что значит число вида #.###?

@shurezz · 05.05.2006, 22:44

#.#### значит напр.: 1,436; 5,3421; 8,4321; 6,34; ... и т.д. где 1<=эточисло<10.

Как когда-то в школе на физике или химии было: 6,02*(10^23) [6,02 умноженное на 10 в 23-ей степени].

Так вот в моем варианте при желании точность конечно будет 8-10 знаков начальных, при желании у небольшом усовершенствовании я думаю можно до 15-20 легко, зато вот 10-ка может быть и в 10-ой и в 15-ой и 433347-ой степени.

Действия, на мой взляд, тоже легко описать, нарп.:

при вычислении корня вычислять корень из первого числа, а количество десятков делить на 2 (конечно надо учесть еще вариант нечетного количества десятков, но об этом счас не будем).

Возведение в степень и того проще, я уже не говорю о сложении, вычитании и так далее...

С уважением, Александр.

06.05.2006, 00:53

Это практически экспоненциальное представление вещественных чисел. Только с увеличенной значимостью экспоненты (той степени десятки). Стандарт IEEE 754 уже содержит в себе экспоненту, и она занимает 10 бит (для 64-битного вещественного числа).
В таких языках как C,Pascal существуют 80-битные вещественные (long double/extended), соответствующие внутреннему 10-байтному представлению данных в i80x87. Диапазон значений для таких данных [3.6*10^–4951, 1.1*10^4932]. Экспонента занимает 15 бит, точность составляет 62 бита - 19-20 цифр. Хотя эти типы данных имеют проблему с переносимостью.
zxc3 говорил о превышении 100 цифр, не думаете ли Вы, что имелась в виду значимость? Ведь 1.1*10^4932 это вообще 4932 цифры. Впрочем, выбор остается за zxc3.
Кстати, я не уточнил выше, что BCD представляет _целые_ числа. Хотя подобный изврат можно применить и здесь - хранить отдельно положение точки.

@shurezz · 06.05.2006, 16:56

Да, согласен.

Хотя, честно говоря, не могу понять, где бы могла понадобится такая точность (20 знака), разве что в NASA

Автор, будьте любезны, подскажите пожалуйста, где Вы это хотите использовать. Любопытство замучило.

Заранее спасибо.

@Vizlim · 06.05.2006, 16:59

zxc3 (14.04.2006)
Подскажите, если кто-нибудь писал программы для работы с длинными числами более 100 цифр.Есть ли что-то готовое в каком-нибудь языке или программе, или нужно писать с "нуля".
Спасибо.

Я писал, программа очень простенькая.... Лучше писать подобную прогу на каком-нибудь из языков Высокого уровня из-за скорости обработки програмного кода и быстрой вычисляемой способности языка... Я думаю, что лучше подайдёт С,С++,Java(но нужно много оперативки если очень большие вычисление Например 100000 символов умножить на 6 значное число)
Вот облегчённая версия программы написаная на JavaScript для чисел не превышающих 255 символов... (сложение и умножение):

PHP/HTML

<html>
<head>
<title>Big number</title>
<script>
var a;
var b;
var c;
var c1;
var f;
var f1;
var f2;
var gh=0;
var cf;
var a1=0;
var ew1=new Array(255);
var ys2=new Array(255);
var wq=new Array(600);
var wqz=new Array(600);    //Основной массив для умножения
var vv=0;                //Help
var gg="";
var pnx=0;
var f5;
var pp=new Array(255);
var cc
var ccz
var ew2=new Array(255);
var ys3=new Array(255);
 
a=prompt("Введите чисело 1:", 999 );
b=prompt("Введите чисело 2:", 999 );
if ((a!=null)&&(b!=0)) {
c=a.length;
c1=b.length;
}
else {
alert("Вы не ввели цифр! Попробуйте заного ввести!!!")
document.location.reload();
}
function A() {
document.all["ttt"].innerHTML=" ";
cf=confirm("Если хочешь сложить нажми Да! Если хочешь умножить нажми Отмена!")
if (cf==true) {
//gh=0;
document.all["ttt"].innerHTML=a+"+"+b+"=";
for(i=0;i<c;i++) {
ew1[i]=a.charAt(i);
}
for(j=0;j<c1;j++) {
ys2[j]=b.charAt(j);
}
f=c+c1;   //+1
f2=f;
for (x=f;x>-1;x--) {    
if ((i!=-1)&&(j!=-1)) {     
//alert("Warning!!!")
wq[x]=gh+parseInt(ew1[i])+parseInt(ys2[j]);
//alert(wq[x])
if (wq[x]>9) { 
//alert("Stranno!!!")    // Если число двойное
gh=parseInt(wq[x]/10);     //wq[x]/10
wq[x]=wq[x]%10
wq[x-1]=gh
}
else {
gh=0;
}
j--;
i--;
}
else 
if ((i!=-1)&&(j==-1)) {
//alert("i--");
wq[x]=gh+parseInt(ew1[i]);
if (wq[x]>9) {     // Если число двойное
gh=parseInt(wq[x]/10);     //wq[x]/10
wq[x]=wq[x]%10
wq[x-1]=gh
}
else {
gh=0;
}
//alert("wq["+x+"]="+wq[x])
i--;
}
else 
if ((i==-1)&&(j!=-1)) {
//alert("j--");
wq[x]=gh+parseInt(ys2[j]);
if (wq[x]>9) {     // Если число двойное
gh=parseInt(wq[x]/10);     //wq[x]/10
wq[x]=wq[x]%10
wq[x-1]=gh
}
else {
gh=0;
}
j--;
}
else 
if ((i==-1)&&(j==-1)) {
//alert("True!!!");
    if (gh==0) {
       wq[x]=" "
    }
    else {
     wq[x]=gh;
gh=0;
    }
}
//alert("i="+i+" j="+j+" x="+x)
}
for (f1=0;f1<f2;f1++) {
document.all["ttt"].innerHTML+=wq[f1];
}
}
//}
else {    // Предназначено для умножения 
    B();
}
}
function B() {
if (c<c1) {
cf=a
a=b
b=cf
c=a.length;
c1=b.length;
}
for(i=0;i<c;i++) {
ew1[i]=parseInt(a.charAt(i));
}
for(j=0;j<c1;j++) {
ys2[j]=parseInt(b.charAt(j));
}
for(z=0;z<256;z++)  ;   }
    else {
     wqz[x]=gh;
gh=0;
    }
}
//alert("i="+i+" j="+j+" x="+x)
}
pp[0]=" ";
for (f1=0;f1<f2;f1++) {
pp[0]+=wqz[f1];
//document.all["ttt"].innerHTML+=wqz[f1]+"
";   //No!!!
}
//document.all["ttt"].innerHTML+="
 
";
  for (u=0;u<600;u++) {
  wqz[u]="";
  }
  } //Close for
   document.all["ttt"].innerHTML=a+"*"+b+"="+pp[0]+"
";    //True!!!
  } //Close else
}   //Close function
</script>
</head>
<body onload="A() 
<center><h1 id="ttt  </h1></center>
 
 
 
By Vadim 2005
</body>
</html>

@mmos · 10.05.2006, 15:23 **[ТС]**

Такая "точность" нужна в криптоаналитике.

Насколько я понял, автор вопроса решил подзаработать на поиске делителей огромных чисел.

Задача очень интересная, но и весьма нетривиальная.

Простой перебор невозможен (Солнышко погаснет или человечество вымрет раньше), а другие методы решения современной науке неизвестны.

Поэтому за решение и предлагают такие деньги.

Однако я сам не утратил надежду довести решение до конца.

Не ради денег, а исключительно из любви к искусству решения задач.

@shurezz · 11.05.2006, 00:25

А можно поподробнее, пожалуйста, про задачу. Хочется тоже мозг понапрячь =).

Заранее спасибо.

11.05.2006, 07:49

http://www.codeproject.com/csharp/biginteger.asp

развлекайтесь

@R1001 · 13.06.2006, 21:42

Есть такой язык Лисп (Lisp) называется по-моему. Помню как один научный сотрудник изучал его лет 15 назад и показывал результаты своего обучения. Например, программа выдала результат факториала уж не помню какого числа, но результатом было число, которое занимало целый лист при печати. Этот язык как раз для таких чисел используется :-)

@BoNiM · 16.06.2006, 14:40

Программы по работе с большими целыми числами на Ассемблере приведены в следующем учебнике:

http://download.ware.ru:8080/win/6853_ASSEMBER.chm

@BoNiM · 16.06.2006, 16:17

А вот еще одна реализация по работе с 256 битными числами (при желании можно модифицировать и на более чем 32 байта) для С++:

http://sources.codenet.ru/file/491/int256.cpp

@zxc3 · 21.06.2012, 09:17

Подскажите, если кто-нибудь писал программы для работы с длинными числами более 100 цифр.Есть ли что-то готовое в каком-нибудь языке или программе, или нужно писать с "нуля".
Спасибо.

@shurezz · 23.06.2012, 20:30

Я сталкивался пару раз. Я просто сохранял число в виде #.#### и отдельную переменную на количество десятков. То есть если число превышает 10, то делим его на десять, а количеству десятков добавляем 1. Вроде того...

23.06.2012, 21:04

То с чем я работал: в JAVA есть весьма удобные классы java.math.BigIntegerBigDecemical которые умеют хранить числа неограниченной длинны и производить операции над ними.
Неудобность заключается в том, что операции только самые базовые (+,-,*,mod, и еще несколько) и классы достаточно медлительные. (Если нужно писать быстрый алгоритм - советую Си говорят там тоже что-то есть)

@mmos 4 / 4 / 2 Регистрация: 06.03.2011 Сообщений: 151
		1
	Работа с большими числами 29.04.2006, 22:48. Показов 9723. Ответов 16 Метки нет (Все метки) Писал-с! Чертовски интересная задача. Делать надо всё с нуля. Но ведь и овчинка выделки стоит. Не так ли? 0

John Paramol
	30.04.2006, 00:42	2
	Если писать самому и качественно, то с применением ассемблера и формата BCD (Binary Coded Decimals - Двоично Кодированные Десятичные). BCD могут быть неупакованные - на каждую десятичную цифру приходится один байт; и упакованные - по 4 бита. Неупакованные BCD обрабатываются процессором по одной цифре за операцию. Кроме обычных комманд для сложения/вычитания есть специфичные для BCD комманды: aaa, aas, aad, aam, daa, das и др. Арифметический сопроцессор может за операцию обрабатывать 10-байтные упакованные BCD (это 18 цифр числа + знаковый байт) Плюс неупакованные BCD легко переводятся в ASCII строку и наоборот. Основы работы с BCD должны быть в любом нормальном учебнике по ассемблеру. Удачи

@shurezz 1 / 1 / 0 Регистрация: 18.11.2010 Сообщений: 139
	03.05.2006, 21:20	3
	А чем Вам не нравится мой вариант с сохранением числа вида #.### и количества десятков отдельно? Объясните. Помоему и места мало и проще некуда. С уважением, Александр. 0

John Paramol
	05.05.2006, 13:48	4
	Никто здесь не говорил, что это кому-то не нравится. А вот мне лично не совсем понятна идея. Что значит число вида #.###?

@shurezz 1 / 1 / 0 Регистрация: 18.11.2010 Сообщений: 139
	05.05.2006, 22:44	5
	#.#### значит напр.: 1,436; 5,3421; 8,4321; 6,34; ... и т.д. где 1<=эточисло<10. Как когда-то в школе на физике или химии было: 6,02*(10^23) [6,02 умноженное на 10 в 23-ей степени]. Так вот в моем варианте при желании точность конечно будет 8-10 знаков начальных, при желании у небольшом усовершенствовании я думаю можно до 15-20 легко, зато вот 10-ка может быть и в 10-ой и в 15-ой и 433347-ой степени. Действия, на мой взляд, тоже легко описать, нарп.: при вычислении корня вычислять корень из первого числа, а количество десятков делить на 2 (конечно надо учесть еще вариант нечетного количества десятков, но об этом счас не будем). Возведение в степень и того проще, я уже не говорю о сложении, вычитании и так далее... С уважением, Александр. 0

John Paramol
	06.05.2006, 00:53	6
	Это практически экспоненциальное представление вещественных чисел. Только с увеличенной значимостью экспоненты (той степени десятки). Стандарт IEEE 754 уже содержит в себе экспоненту, и она занимает 10 бит (для 64-битного вещественного числа). В таких языках как C,Pascal существуют 80-битные вещественные (long double/extended), соответствующие внутреннему 10-байтному представлению данных в i80x87. Диапазон значений для таких данных [3.610^–4951, 1.110^4932]. Экспонента занимает 15 бит, точность составляет 62 бита - 19-20 цифр. Хотя эти типы данных имеют проблему с переносимостью. zxc3 говорил о превышении 100 цифр, не думаете ли Вы, что имелась в виду значимость? Ведь 1.1*10^4932 это вообще 4932 цифры. Впрочем, выбор остается за zxc3. Кстати, я не уточнил выше, что BCD представляет _целые_ числа. Хотя подобный изврат можно применить и здесь - хранить отдельно положение точки.

@shurezz 1 / 1 / 0 Регистрация: 18.11.2010 Сообщений: 139
	06.05.2006, 16:56	7
	Да, согласен. Хотя, честно говоря, не могу понять, где бы могла понадобится такая точность (20 знака), разве что в NASA Автор, будьте любезны, подскажите пожалуйста, где Вы это хотите использовать. Любопытство замучило. Заранее спасибо. 0

@mmos 4 / 4 / 2 Регистрация: 06.03.2011 Сообщений: 151
	10.05.2006, 15:23 [ТС]	9
	Такая "точность" нужна в криптоаналитике. Насколько я понял, автор вопроса решил подзаработать на поиске делителей огромных чисел. Задача очень интересная, но и весьма нетривиальная. Простой перебор невозможен (Солнышко погаснет или человечество вымрет раньше), а другие методы решения современной науке неизвестны. Поэтому за решение и предлагают такие деньги. Однако я сам не утратил надежду довести решение до конца. Не ради денег, а исключительно из любви к искусству решения задач. 0

@shurezz 1 / 1 / 0 Регистрация: 18.11.2010 Сообщений: 139
	11.05.2006, 00:25	10
	А можно поподробнее, пожалуйста, про задачу. Хочется тоже мозг понапрячь =). Заранее спасибо. 0

Messir
	11.05.2006, 07:49	11
	http://www.codeproject.com/csharp/biginteger.asp развлекайтесь

	23.06.2012, 21:04

@R1001 2 / 2 / 0 Регистрация: 09.09.2009 Сообщений: 118
	13.06.2006, 21:42	12
	Есть такой язык Лисп (Lisp) называется по-моему. Помню как один научный сотрудник изучал его лет 15 назад и показывал результаты своего обучения. Например, программа выдала результат факториала уж не помню какого числа, но результатом было число, которое занимало целый лист при печати. Этот язык как раз для таких чисел используется :-) 0

@BoNiM 7 / 7 / 1 Регистрация: 06.12.2006 Сообщений: 329
	16.06.2006, 14:40	13
	Программы по работе с большими целыми числами на Ассемблере приведены в следующем учебнике: http://download.ware.ru:8080/win/6853_ASSEMBER.chm 0

@BoNiM 7 / 7 / 1 Регистрация: 06.12.2006 Сообщений: 329
	16.06.2006, 16:17	14
	А вот еще одна реализация по работе с 256 битными числами (при желании можно модифицировать и на более чем 32 байта) для С++: http://sources.codenet.ru/file/491/int256.cpp 0

@zxc3 0 / 0 / 0 Регистрация: 07.09.2011 Сообщений: 7
	21.06.2012, 09:17	15
	Подскажите, если кто-нибудь писал программы для работы с длинными числами более 100 цифр.Есть ли что-то готовое в каком-нибудь языке или программе, или нужно писать с "нуля". Спасибо. 0

@shurezz 1 / 1 / 0 Регистрация: 18.11.2010 Сообщений: 139
	23.06.2012, 20:30	16
	Я сталкивался пару раз. Я просто сохранял число в виде #.#### и отдельную переменную на количество десятков. То есть если число превышает 10, то делим его на десять, а количеству десятков добавляем 1. Вроде того... 0

acrobat
	23.06.2012, 21:04	17
	То с чем я работал: в JAVA есть весьма удобные классы java.math.BigIntegerBigDecemical которые умеют хранить числа неограниченной длинны и производить операции над ними. Неудобность заключается в том, что операции только самые базовые (+,-,*,mod, и еще несколько) и классы достаточно медлительные. (Если нужно писать быстрый алгоритм - советую Си говорят там тоже что-то есть)