<?xml version='1.0' encoding="utf-8"?>
      <rss version='2.0'>
      <channel>
      <title>Форум на Исходниках.RU</title>
      <link>https://forum.sources.ru</link>
      <description>Форум на Исходниках.RU</description>
      <generator>Форум на Исходниках.RU</generator>
  	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=72091&amp;view=findpost&amp;p=561808</guid>
        <pubDate>Fri, 31 Dec 2004 11:52:15 +0000</pubDate>
        <title>Длинная арифметика - решение математики</title>
        <link>https://forum.sources.ru/index.php?showtopic=72091&amp;view=findpost&amp;p=561808</link>
        <description><![CDATA[mikv: ИМХО, копирайты-то поставить надо. Это код из книги С.М.Окулова.<br><br>и const osn  - имелся ввиду не порядок, а основание системы счисления, в которой оперируем. <br>MaxDig - мкасимальное количество цифр.]]></description>
        <author>mikv</author>
        <category>Pascal: Математика</category>
      </item>
	
      <item>
        <guid isPermaLink='true'>https://forum.sources.ru/index.php?showtopic=72091&amp;view=findpost&amp;p=506463</guid>
        <pubDate>Tue, 09 Nov 2004 17:41:35 +0000</pubDate>
        <title>Длинная арифметика - решение математики</title>
        <link>https://forum.sources.ru/index.php?showtopic=72091&amp;view=findpost&amp;p=506463</link>
        <description><![CDATA[Азат: <span class="tag-color tag-color-named" data-value="blue" style="color: blue"><strong class='tag-b'><span class='tag-size' data-value='11' style='font-size:11pt;'>Длинная Арифметика</span></strong></span><br>
<br>
При написании программ на паскале часто приходится сталкиваться с такой проблемой, что стандартных типов не хватает для работы с большими числами. Даже типа int64, который есть в TMT паскале, может не хватить во многих случаях. Чтобы работать с большими числами существует прием, который называется длинной арифметикой. Для наглядного объяснения сразу начнем писать модуль для работы с длинной арифметикой. Для начала напишем следующее банальное выражение:<br>
<div class='tag-code'><span class='pre_code'></span><div class='code  code_collapsed ' title='Подсветка синтаксиса доступна зарегистрированным участникам Форума.' style=''><div><div><ol type="1"><div class="code_line">unit Long;</div><div class="code_line">interface</div><div class="code_line">const</div><div class="code_line">&nbsp;&nbsp;osn = 10000; &nbsp; {Порядок каждого числа}</div><div class="code_line">&nbsp;&nbsp;MaxDig = 1000; {Максимальное количество элементов}</div><div class="code_line">type</div><div class="code_line">&nbsp;&nbsp;TLong = array[0..MaxDig] of integer; {Длинное число}</div><div class="code_line">implementation</div><div class="code_line">end.</div></ol></div></div></div></div><script>preloadCodeButtons('1');</script><br>
<br>
Длинное число хранится в массиве типа TLong. В каждом элементе хранится по i цифр длинного числа. i вычисляется по формуле:<br>
<br>
i = lg(osn)<br>
<br>
При osn = 10000 i равно 4. <br>
<br>
В нулевом элементе массива хранится количество задействованных элементов, а само число записывается в массив в обратном порядке. То есть если мы запишем в массив А число 123456789, то массив будет выглядеть так:<br>
<div class='tag-code'><span class='pre_code'></span><div class='code  code_collapsed ' title='Подсветка синтаксиса доступна зарегистрированным участникам Форума.' style=''><div><div><ol type="1"><div class="code_line">a[0] = 3</div><div class="code_line">a[1] = 6789;</div><div class="code_line">a[2] = 2345;</div><div class="code_line">a[3] = 1;</div></ol></div></div></div></div><br>
<br>
Теперь надо написать две самые необходимые процедуры. Это процедуры чтения и вывода длинных чисел.<br>
<br>
<div class='tag-code'><span class='pre_code'></span><div class='code  code_collapsed ' title='Подсветка синтаксиса доступна зарегистрированным участникам Форума.' style=''><div><div><ol type="1"><div class="code_line">procedure Long_Read(var f:text; var a:TLong); {Читает длинное число из консоли или из файла}</div><div class="code_line">var &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {откуда будет производиться чтение, зависит от переменной F}</div><div class="code_line">&nbsp;&nbsp;ch:char;</div><div class="code_line">&nbsp;&nbsp;i:integer;</div><div class="code_line">begin</div><div class="code_line">&nbsp;&nbsp;FillChar(a,Sizeof(A),0); &nbsp; &nbsp; &nbsp; &nbsp; {Заполняем массив нулями}</div><div class="code_line">&nbsp;&nbsp;repeat &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {Пропускаем НЕ цифры вначале файла} </div><div class="code_line">&nbsp;&nbsp; &nbsp;Read(f,ch); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</div><div class="code_line">&nbsp;&nbsp;until ch in [&#39;0&#39;..&#39;9&#39;];</div><div class="code_line">&nbsp;&nbsp;while ch in [&#39;0&#39;..&#39;9&#39;] do &nbsp; &nbsp; &nbsp; &nbsp;{Начинаем читать цифры}</div><div class="code_line">&nbsp;&nbsp; &nbsp;begin</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;for i := a[0] downto 1 do</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;begin</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;a[i+1] := a[i+1]+(Longint(a[i])*10) div osn; &nbsp;{Записываем цифры в массив}</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;a[i] &nbsp; := (Longint(a[i])*10) mod osn;</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;end;</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;a[1] := a[1]+Ord(ch)-ord(&#39;0&#39;);</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;if a[a[0]+1]&#62;0 then inc(a[0]); {Если элемент текущий элемент заполнили, то переходим к следующему}</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;Read(f,ch) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {Читаем след. символ} &nbsp;</div><div class="code_line">&nbsp;&nbsp; &nbsp;end</div><div class="code_line">end;</div><div class="code_line">{-----------------------------------------------------------------------------------------}</div><div class="code_line">procedure Long_Write(var f:text; const a:TLong); &nbsp; &nbsp; {Выводит число в файл или в консоль}</div><div class="code_line">var</div><div class="code_line">&nbsp;&nbsp;ls,s:string;</div><div class="code_line">&nbsp;&nbsp;i:integer;</div><div class="code_line">begin</div><div class="code_line">&nbsp;&nbsp;Str(Osn div 10,ls); &nbsp;{Преобразуем в стоку osn div 10}</div><div class="code_line">&nbsp;&nbsp;Write(f,A[A[0]]); &nbsp; &nbsp;{Выводим последний элемент}</div><div class="code_line">&nbsp;&nbsp;for i := a[0]-1 downto 1 do</div><div class="code_line">&nbsp;&nbsp; &nbsp;begin</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;Str(a[i],s); &nbsp; &nbsp; {Преобразуем в стороку каждый след. элемент}</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;while Length(s)&#60;Length(ls) do s := &#39;0&#39;+s; &nbsp;{Если длина строки не равна lg(osn), то ставим перед ней 0}</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;Write(f,s); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {Печатаем строку}</div><div class="code_line">&nbsp;&nbsp; &nbsp;end;</div><div class="code_line">&nbsp;&nbsp;WriteLn</div><div class="code_line">end;</div></ol></div></div></div></div><br>
<br>
Процедура Long_Read читает длинное число из текстового файла в переменную А, а Long_Write записывает число из А в файл. <br>
Если поставить input(output для Long_Write) в качестве первого параметра, то чтение и запись будут выполняться с консоли.<br>
<br>
Чтобы можно было с этими считанными числами что-то делать, надо написать процедуры сложения, вычитания, умножения, деления, операции больше, меньше и т. п.<br>
<br>
Арифметические операции производятся столбиком (вспоминаем 3 класс). Операции &quot;больше-меньше&quot; реализованы на том же уровне, т.е. поразрядное сравнение. Все это скомпонованное, отлаженное, проверенное я кладу в модуле LongMath.pas, в который добавлены операции с комплексными числами.<br>
<br>
...и вот на всякий случай маленький примерчик...<br>
<div class='tag-code'><span class='pre_code'></span><div class='code  code_collapsed ' title='Подсветка синтаксиса доступна зарегистрированным участникам Форума.' style=''><div><div><ol type="1"><div class="code_line">uses LongMath;</div><div class="code_line">var</div><div class="code_line">&nbsp;&nbsp;a,b,c : TLong;</div><div class="code_line">&nbsp;&nbsp;x,y,z : TComplex;</div><div class="code_line">&nbsp;&nbsp;</div><div class="code_line">begin</div><div class="code_line">&nbsp;&nbsp;WriteLn (&#39;Введите 2 длинных числа:&#39;);</div><div class="code_line">&nbsp;&nbsp;Long_Read(input,a); {Читаем с клавиатура а и b}</div><div class="code_line">&nbsp;&nbsp;Long_Read(input,b);</div><div class="code_line">&nbsp;&nbsp;if Long_Equal(a,b) then WriteLn(&#39;Числа a и b равны&#39;) {Сравниваем числа}</div><div class="code_line">&nbsp;&nbsp;else</div><div class="code_line">&nbsp;&nbsp; &nbsp;begin</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;if Long_Less(a,b) then WriteLn(&#39;a меньше b&#39;);</div><div class="code_line">&nbsp;&nbsp; &nbsp; &nbsp;if Long_Above(a,b) then WriteLn(&#39;a больше b&#39;);</div><div class="code_line">&nbsp;&nbsp; &nbsp;end;</div><div class="code_line">&nbsp;&nbsp;WriteLn (&#39;Нажмите Ввод для продолжения&#39;);</div><div class="code_line">&nbsp;&nbsp;ReadLn;</div><div class="code_line">&nbsp;</div><div class="code_line">&nbsp;&nbsp;Long_Add(a,b,c); &nbsp; &nbsp;{c := a+b}</div><div class="code_line">&nbsp;&nbsp;WriteLn(&#39;Сумма x и y равна &#39;); {Выводим сумму на экран}</div><div class="code_line">&nbsp;&nbsp;Long_Write (output, c);</div><div class="code_line">&nbsp;</div><div class="code_line">&nbsp;&nbsp;WriteLn (&#39;Нажмите Ввод для продолжения&#39;);</div><div class="code_line">&nbsp;&nbsp;readln;</div><div class="code_line">end.</div></ol></div></div></div></div><br>
<br>
<span class="tag-color tag-color-named" data-value="blue" style="color: blue">(V. Приведенный модуль работает с беззнаковыми числами, впрочем в задачах, в которых нужны именно ОЧЕНЬ большие числа, они почти всегда больше нуля.)</span>]]></description>
        <author>Азат</author>
        <category>Pascal: Математика</category>
      </item>
	
      </channel>
      </rss>
	