OberonCore
https://forum.oberoncore.ru/

подскажите по вопросу с большими числами
https://forum.oberoncore.ru/viewtopic.php?f=27&t=307		 Страница 1 из 1
Автор:  ___ [ Вторник, 26 Сентябрь, 2006 15:39 ]
Заголовок сообщения:  подскажите по вопросу с большими числами
создавал совсем простенький проект в VS2005 на с# (ASP.NET)
особо в них не понимаю
вообщем столкнулся с тем что нехватает длины int32 и int64
нужно больше
вот вопрос
как понимаю других числовых типов там нету
нужен бооооольшой натуральный ряд с нулем
может есть какие теории по работе с такими числами или др не шибко сложные средства как это обойти?
Автор:  Info21 [ Вторник, 26 Сентябрь, 2006 19:24 ]
Заголовок сообщения: 
Не понял.

Если нужно просто посчитать что-то, можно взять Блэкбокс, модуль Integers.

Арифметика произвольной точности много где реализована. Теория -- например, у Кнута.
Автор:  Евгений Темиргалеев [ Пятница, 29 Сентябрь, 2006 00:31 ]
Заголовок сообщения: 
Если немного уточнить, то у Кнута дана многократная точность (на массивах)... а произвольная вынесена в виде упражнения (и как все говорят, требует связного распределения, тобишь списков).
Автор:  Info21 [ Пятница, 29 Сентябрь, 2006 18:45 ]
Заголовок сообщения: 
Ох уж эти все :)))))

Массив нужной длины всегда под результат можно распределить -- как и делается, например, в модуле Integer.

В классическом Обероне, где нет открытых массивов, проще со списками.

Переложить кнутовские алгоритмы на списки -- косметика: там все проходы по "цифрам" последовательные.
Автор:  Евгений Темиргалеев [ Пятница, 29 Сентябрь, 2006 20:58 ]
Заголовок сообщения: 
Гм... хотя тема не совсем про это, раз уж разговор зашел, хочу кое-что обсудить.

Как я понимаю различие между многократной (multiple) и произвольной (arbitrary) точностью, многократная - это когда существует априори граница для максимальной длины числа (если и могут быть числа длиннее - то вероятность их появления мала). И она не так уж велика (в смысле выбранного основания системы, напр. 2^15). Произвольная - это когда предполагаемые длины неизвестны и могут часто появляться и "очень длинные" числа.

Вопрос выбора представления в виде массива или списка основывается не на том, где что проще использовать, а в эффективности использования этих представлений. (Про эффективность я пока говорю только с теоретической точки зрения; на конкретных практических задачах сравнивать эти подходы пока не доводилось.) И так, если говорить об операциях сложения и вычитания, то при использовании массивов, время пропорционально max(L(a), L(b)), а при использовании списков с перекрытием min(L(a), L(b)); L(x) - длина числа. Поэтому когда приходится, например, складывать очень длинное число с коротким, разница должна проявиться существенная.

(благодаря встроенной сборке мусора) Идея с перекрытием списков может быть реализована элементарно. При этом, если использовать подход к реализации как в Integers, заключающийся в том, что создаваемые представления чисел неизменны, вся "конструкция" оказывается законченной и безопасной.

Однако, я думаю, на практике должны попадаться задачи типа посчитать сумму или произведение ряда чисел. Здесь такой подход (неизменность) чреват дополнительными временными затратами и излишним засорением памяти. Поэтому пригодились бы такие операции как "прибавить к" или "умножить на", которые использовали бы один из аргументов в качестве приемника результата; если говорить на C++, += и *=. Ввести такие операции не сложно. Однако, теперь нужно быть увереным, что список цифр аргумента-приемника не перекрыт списками цифр других чисел (*).

И вот, собственно, тот "философский" вопрос, который я хотел обсудить: "Быть или не быть?". С одной стороны, гарантию выполнения (*) можно возложить на клиента модуля, тобишь на нас с вами - программистов, которым как человекам :) свойственно ошибаться. (Но ето не наши методы!) С другой стороны, какой подход применить, чтобы (*) можно было проверять эффективно программными средствами?

Я в свое время использовал счетчики ссылок в узлах, но это было на C++ - без сборки мусора; но с этими счетчиками про эффективное использование памяти и min(L(a), L(b)) можно забыть сразу... В общем какие будут ваши мнения, господа?
Автор:  Иван Горячев [ Суббота, 30 Сентябрь, 2006 06:02 ]
Заголовок сообщения: 
Евгений Темиргалеев писал(а):
В общем какие будут ваши мнения, господа?

Накатать интерфейс к GMP?
Автор:  Борис Рюмшин [ Суббота, 30 Сентябрь, 2006 13:16 ]
Заголовок сообщения: 
Чё я давно предлагаю сделать. :):):):):)
Автор:  Иван Горячев [ Понедельник, 02 Октябрь, 2006 01:21 ]
Заголовок сообщения: 
Я даже пытался, но упёрся в unsigned long :( Приведения типов и процедуры-обёртки тут явно не катят, ибо быстродействие, а безнаковых целых в ББ нет :(
Автор:  Vlad [ Понедельник, 02 Октябрь, 2006 08:28 ]
Заголовок сообщения: 
Евгений Темиргалеев писал(а):
С другой стороны, какой подход применить, чтобы (*) можно было проверять эффективно программными средствами?


COW? При попытке модификации элемента списка весь список копируется при количестве ссылок на него > 1. Такой подход используется в некоторых реализациях std::string. Скорее всего окажется неэффективен в случае многопоточности.

Евгений Темиргалеев писал(а):
Я в свое время использовал счетчики ссылок в узлах, но это было на C++ - без сборки мусора; но с этими счетчиками про эффективное использование памяти и min(L(a), L(b)) можно забыть сразу... В общем какие будут ваши мнения, господа?


Не очень понял, чем тебе помешали счетчики ссылок, если только ты не считал ссылки на каждый элемент.
Автор:  Евгений Темиргалеев [ Понедельник, 02 Октябрь, 2006 20:46 ]
Заголовок сообщения: 
Речь шла именно про счетчик в каждом узле, чтобы сделать перекрывающиеся списки, для которых надо копировать не весь список, а только "хвост", который отностится к нескольким спискам.
Автор:  Vlad [ Четверг, 12 Октябрь, 2006 21:35 ]
Заголовок сообщения: 
Евгений Темиргалеев писал(а):
Речь шла именно про счетчик в каждом узле, чтобы сделать перекрывающиеся списки, для которых надо копировать не весь список, а только "хвост", который отностится к нескольким спискам.


ИМХО это очень неэффективный подход.
Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/