Большие числа

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

Re: Большие числа

Сообщение Лекс Айрин » 11.01.2019 08:24:01

Vadim,это да... Но все равно странно.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5307
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Большие числа

Сообщение iskander » 11.01.2019 11:03:26

Evgen, спасибо, я так и подумал, что это олимпиадная задачка.
Чем она забавна: пусть для определенности коробка имеет размеры 20х20х25 см.
Тогда в объеме видимой части вселенной поместится 3,5*10^82 коробочек(если вика нам не врет).
Соответственно для размещения всех коробочек потребуется 2,86*10^9917 таких вселенных.
Нехилый склад получился :mrgreen: . В общем напомнило рыбу, которая сидела на дереве.
По вашим вопросам: в стандартной установке FPC MPArith нет, это сторонняя библиотека.
Есть модуль gmp, но для его использования необходимо наличие библиотеки gmp на
целевой машине.

PS: если собираетесь участвовать в олимпиадах, про длинную арифметику почитайте обязательно.
Последний раз редактировалось iskander 11.01.2019 11:27:13, всего редактировалось 1 раз.
iskander
постоялец
 
Сообщения: 142
Зарегистрирован: 08.01.2012 18:43:34

Re: Большие числа

Сообщение Снег Север » 11.01.2019 11:20:26

Evgen писал(а):Сначала хочу спросить включена ли библиотека MPArith автоматически у FRC, ели нет, то как ее подключить?

Я дал ссылку в моем первом сообщении в теме. Качаете архив, распаковываете в любое подходящее место, а в проекте указываете путь к этому месту...
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 1740
Зарегистрирован: 27.11.2007 16:14:47

Re: Большие числа

Сообщение Evgen » 12.01.2019 01:18:03

Библиотечку MPArith Снег Север я скачал, но куда ее пристроить.
Длинную арифметику читаю.
И всем спасибо за советы
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

Re: Большие числа

Сообщение Снег Север » 12.01.2019 07:14:58

Evgen, вы просто используете из нее нужные файлы. В своем примере iskander написал, какие и дал пример использования. В свойствах проекта у вас есть настройки, где искать дополнительные юниты, там прописываете путь к месту, куда распаковали MPArith. Или, на худой конец, копируете нужные файлы прямо к своему проекту.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 1740
Зарегистрирован: 27.11.2007 16:14:47

Re: Большие числа

Сообщение Vadim » 12.01.2019 13:10:33

Evgen
По поводу MPArith.
Если Вы по каким-то обстоятельствам используете текстовую IDE из FreePascal, то из скачанного архива скопируйте себе в каталог своей программы файлы:
- mp_types, btypes (он нужен для предыдущего модуля), mp_base, mp_prng.
- *.inc файлы.
Vadim
долгожитель
 
Сообщения: 3466
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие числа

Сообщение Evgen » 13.01.2019 04:48:09

Спасибо, я многому научился у ВАС
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

Re: Большие числа

Сообщение Evgen » 19.01.2019 03:40:59

И снова я прошу помощи. Вот такая задачка.
На промежутке А,В найти все простые числа (1 сек., 256 МiБ; 1≤A≤10е12, A≤B, B−A≤2•10е6.)
Вот мой код:
program prostere;
type ms=array[1..1000000] of byte;
var a,b:^longint;i,j,k:longint; s:^ms;
begin
new(a); new(b); new(s); readln(a^,b^);
if (a^=b^) and (a^=1) then k:=0 else
if (a^=b^) and (a^=2) then k:=1 else
if (a^=1) and (b^=2) then k:=1 else
if (a^=b^) and (b^ mod 2 = 0) then k:=0 else
if b^-a^ = 2*10e6 then k:=0 else

begin
s^[1]:=0;
for i:=2 to b^ do s^[i] :=1;
i:=2;
while i*i<b^ do begin
if s^[i]=1 then begin
j:=i*i; while j<=b^ do begin
s^[j]:=0; j:=j+i end;
end;
i:=i+1;
end;
k:=0;
for i:=a^ to b^ do
if s^[i]=1 then k:=k+1; end;
writeln(k);
dispose(s);
dispose(a);
dispose(b);
end.

Использовал решето Ератосфена (но туту максимальное А -10е7 (больше елементов в масиве не проходит).
Как поступить? Может хто поможет.
С уважением Еvgen
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

Re: Большие числа

Сообщение Снег Север » 19.01.2019 07:00:57

Evgen, главное что мне непонятно в вашем коде - зачем вы постоянно используете указатели??? Это требование ваших преподавателей? Эти разыменования, освобождение памяти - это же неудобно и просто лишнее.
По существу вопроса - в FPC есть
type Int64 = - 9223372036854775808..9223372036854775807
который должен решить вашу проблему с диапазоном чисел в той задаче.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 1740
Зарегистрирован: 27.11.2007 16:14:47

Re: Большие числа

Сообщение Дож » 19.01.2019 09:12:04

Evgen, 1. для отдельной задачи лучше заводить отдельную тему 2. код желательно окружать тегом code.

По задаче: решето Эратосфена напрямую не подходит, т.к. не хватит ни пямяти, ни времени его заполнить. Предлагаю более подходящий алгоритм.

Идея алгоритма строится вокруг простого утверждения: любое составное число в диапазоне от 1 до B имеет нетривиальный делитель от 2 до Sqrt(B) (квадратный корень из B). Доказательство утверждения тривиально.

В таблице s, как и раньше, будем "хранить простоту чисел", но для диапазона от A до B. Размер таблицы будет равен B-A+1<=2MB+1. Все элементы таблицы изначально равны 1 ("считаем простыми").

Заполняем таблицу аналогично решету: перебираем все числа i в диапазоне от 2 до Sqrt(B), и для всех чисел 2i, 3i, 4i, ... (составные числа с делителем I), попавших в диапазон от A до B, записываем в таблицу 0.

Ещё раз: s^[i] равно 1, если для A+i ещё не найден нетривиальный делитель, и 0, если найден. Далее, как и в случае с решетом, нужно сосчитать число единиц в таблице.

Время работы O((B-A)*log(Sqrt(B))) укладывается в 1 секунду.

Далее советы по реализации:
1. Использовать Int64 вместо longint (возможно, придётся отказаться от for-to циклов в пользу while-do)
2. Вместо вычисления корня встроенной функцией Sqrt лучше аккуратно руками вычислить какую-нибудь оценку, например, так:
Код: Выделить всё
  // Compute M: Sqr(B) <= M <= 10000000
  M := 1;
  while M * M < B do
    M := M * 2;

3. Первое число последовательности 2i, 3i, 4i, ..., попавшее в диапазон от A до B, примерно равно ((A+i-1) div i) * i
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 756
Зарегистрирован: 12.10.2008 16:14:47

Re: Большие числа

Сообщение iskander » 19.01.2019 15:20:39

Дож писал(а):2. Вместо вычисления корня встроенной функцией Sqrt лучше аккуратно руками вычислить какую-нибудь оценку, например, так:

Зачем?
iskander
постоялец
 
Сообщения: 142
Зарегистрирован: 08.01.2012 18:43:34

Re: Большие числа

Сообщение Дож » 19.01.2019 22:02:15

iskander, вы готовы привести строгое доказательство какого-нибудь утверждения про точность Sqrt(B) на всех архитектурах, со ссылкой на документацию и т.д.? Если да, то приводите.
Код: Выделить всё
var
  I: Int64;
  F: Single;
begin
  I := 1125899991909595;
  F := Sqrt(I);
  Writeln((F + 1) * (F + 1) < I);
end.

Код: Выделить всё
D:\data\temp>fpc sqrt.pas && sqrt.exe
Free Pascal Compiler version 3.0.4 [2017/10/06] for i386
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling sqrt.pas
Linking sqrt.exe
8 lines compiled, 0.0 sec, 25504 bytes code, 1252 bytes data
TRUE
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 756
Зарегистрирован: 12.10.2008 16:14:47

Re: Большие числа

Сообщение iskander » 19.01.2019 23:23:03

Дож, я вас как-то задел своим вопросом, к чему такой пафос?
Вы просто пропустили в своем посте момент зачем.
И да, в вашем последнем примере число I на 4 порядка больше, чем по условию задачи.
Корень из которого вы зачем-то приводите к Single, куда он точно не влезет.
К тому же интересен не сам корень, а его верхняя граница, что-то вроде Trunc(Sqrt(I)) + 1;
iskander
постоялец
 
Сообщения: 142
Зарегистрирован: 08.01.2012 18:43:34

Re: Большие числа

Сообщение Дож » 19.01.2019 23:31:24

Не задели, меня абсолютно искренне интересует строгое доказательство :)

И да, в вашем последнем примере число I на 4 порядка больше, чем по условию задачи.

Я в курсе. Готовы доказать, что для I из диапазона от 1 до 10e12+10e6 на всех процессорах результат будет достаточно точным? А если найду контрпример?
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 756
Зарегистрирован: 12.10.2008 16:14:47

Re: Большие числа

Сообщение Evgen » 20.01.2019 01:27:58

Уважаемый Снег Север, это опять олимпиадная задача и указатели я использовал потому что думал увеличить память ( может я что-то не так понимаю, ведь учусь сам). До указателей я попробовал несколько кодов программы с типом int64 (они решают проблему диапазона чисел, но на третьем тесте выдают уведомление либо Лимит времени, либо Лимит памяти. Вот эти коды:
Код: Выделить всё
program prostere;
var s:ansistring; a,b,i,j,k:int64;
begin
readln(a,b);  s:='0';
for i:=2 to b do s:=s+'1';
i:=2;
while i*i<b do begin
   if s[i]='1' then   begin
   j:=i*i; while j<=b do begin
                s[j]:='0'; j:=j+i end;
                end;
   i:=i+1;
   end;
   k:=0;
  for i:=a to b do
   if s[i]='1' then k:=k+1;
   writeln(k);
   end.
Тут лимит времени (1.043 сек)

А вот другой код
Код: Выделить всё
program prostere;
var s:array of byte; a,b,i,j,k:int64;
begin
readln(a,b);  setlength(s,b+1);
      s[1]:=0;
for i:=2 to b do s[i] :=1;
i:=2;
while i*i<b do begin
   if s[i]=1 then   begin
   j:=i*i; while j<=b do begin
                s[j]:=0; j:=j+i end;
                end;
   i:=i+1;
   end;
   k:=0;
  for i:=a to b do
   if s[i]=1 then k:=k+1;    {end;}
   writeln(k);
   s := nil;
end.

В этом коде Лимит памяти (307.914 МIБ, а можна максимум 1 сек., 256 МіБ).
Есть и другие варианты кодов, но не буду Вас утомлять, потому что результат всегда один и тот же (проходят два теста); кстати и с указателями с типом int64 Лимит памяти на 3 тесте.
Спор Дожа и Iskandera мне не очень понятный, но постараюсь реализовать алгоритм Iskandera.
Пока всем спасибо.
Буду думать и осмысливать ваши "порады", то есть советы (за ошибки звените, русский изучал сам).
Следующий раз открою новую тему
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

Пред.След.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4

Рейтинг@Mail.ru