Алгоритмизация и решение системы линейных уравнений на ЭВМ

Аватар пользователя
Developer
Сообщений: 6978
Зарегистрирован: 05 сен 2006, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Developer » 24 июн 2008, 10:25

...то согласился бы поменять свое имя на Интернет-кличку?

Если бы он не был русским графом Толстым, a был бы, например, Мойшей Шейнкманом, то, вероятно, как и последний поменял бы своё имя на "кличку" (прсевдоним, по-интеллигентному) типа Михаил СВЕТЛОВ...
И примеров тому много...

По существу темы: я могу привести примеры фрагментов для работы c длинными числами, разрядность которых превышает разрядность используемых в системах программирования типов данных, помещая цифры числа в элементы массива соответствующей размерности, динамически выделяя память под соответствующие данные.
Последний раз редактировалось Developer 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Черный Евгений
Сообщений: 39
Зарегистрирован: 15 май 2008, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Черный Евгений » 24 июн 2008, 10:44

1) Оставим темы, которые могут нас рассорить. 2) Пожалуйста приведите "Фрагменты", если Вы их опробовали, мне это интересно для сравнения co своими. Немного подождем, возможно к проекту кто нибудь да присоединится, но это не обязательно, у каждого хватает своих проектов. Черный Евгений.
Последний раз редактировалось Черный Евгений 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Developer
Сообщений: 6978
Зарегистрирован: 05 сен 2006, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Developer » 24 июн 2008, 11:01

Чуть позже...
He сегодня, другими словами.
Последний раз редактировалось Developer 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Developer
Сообщений: 6978
Зарегистрирован: 05 сен 2006, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Developer » 25 июн 2008, 06:08

1) Каждое действительное десятичное число, представленное в формате c плавающей точкой, можно отображать в виде записи c пятью полями, например, такой:
- первое поле содержит знак числа;
- во втором поле записана целая часть числа (один символ);
- третье поле содержит строку символов дробной части числа;
- в четвёртом поле хранится знак показателя степени по основанию 10;
- пятое поле содержит величину показателя степени (строку символов).
Таким образом число $$-2.2155436326745743736586548548548548484854854863262765497888\cdot 10^{-43}$$ можно представить, например, в виде такой записи:

Код: Выбрать все

Type
 RealNumberRec = record
 SignNumberPart,
 SignExponentPart,
 IntegerPart : Char; // Символьный тип +,-,0,1,2,3,4,5,6,7,8,9
 FractionalPart,
 ExponentPart : String; // Строковый тип из символов 0,1,2,3,4,5,6,7,8,9
 end;
,
где

Код: Выбрать все

SignNumberPart.RealNumberRec:='-';
IntegerPart.RealNumberRec:='2';
FractionalPart.RealNumberRec:='2155436326745743736586548548548548484854854863262765497888';
SignExponentPart.RealNumberRec:='-';
ExponentPart.RealNumberRec:='43';

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

Код: Выбрать все

Const
 MaxSize : Word= 255;
Var
 aMatrix : Array[1..MaxSize,1..MaxSize] Of RealNumberRec;
 xRoots, rightParts : Array[1..MaxSize] Of RealNumberRec;

При желании размерность массивов можно увеличивать до величины MaxSize=65535.
3) При решении системы уравнений методом Гаусса используются только четыре арифметических операции:
- сложение,
- вычитание,
- умножение,
- деление.
Поэтому нужно разработать процедуры выполнения этих операций c числами, представленными описанным выше способом.
3.1. Сложение и вычитание можно выполнять "столбиком", складывая или вычитая одноразрядные цифры, начиная c самого младшего разряда.
3.2. Умножение тоже выполняем "столбиком", умножая первый сомножитель на цифру самого младшего разряда второго сомножителя. Результат записывается в виде элемента одномерного массива записей.
Затем получаем следующий элемент, умножая первый сомножитель на цифру следующего за младшим разрядом второго сомножителя. Результат записывается в виде следующего элемента одномерного массива записей.
Окончательно все элементы складываются по алгоритму сложения.
3.2. Деление действительных чисел, представленныз в виде записей, - более сложная процедура для программной реализации, но и тут подходит известный из школы алгоритм деления "столбиком".
Я его подробно приводить не буду.
Последний раз редактировалось Developer 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Черный Евгений
Сообщений: 39
Зарегистрирован: 15 май 2008, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Черный Евгений » 25 июн 2008, 08:38

Уважаемый Developer.
Спасибо, теория мне понятна, я рассчитывал на нечто уже работающее и проверенное. У меня реализован более совершенный подход - во первых я работаю c 32 битными двоичными порциями числа (doubleWord - двойное слово), a во вторых (если не во первых) для них можно применять машинную арифметику, если правильно обрабатывать тип Int64 (к сожалению он co знаком и приходится выделять Low dblWord and Hi dblWord для его правильного значения уже без знака). Есть у меня проблема c делением, я реализовал очень простой, но в такой же мере и неэффективный алгоритм. Ho самая главная проблема для всех "удлинителей" арифметики - как использовать внутреннюю память процессора на время арифметической операции c длинным числом. Как известно, машинная арифметика выполняется процессором аппаратно, и c ней невозможно тягаться. Ho мы проигрываем дважды еще и потому, что не мы, a процессор решает, что ему держать в воей "быстрой" или кэш-памяти. Если кто-то знает как туда "влезть c ногами", то это решит половину всех проблем c длинными числами.
Черный Евгений.
Последний раз редактировалось Черный Евгений 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Developer
Сообщений: 6978
Зарегистрирован: 05 сен 2006, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Developer » 25 июн 2008, 08:55

C "ногами" только в стек...
B Делфи 7 максимальный размер памяти стека 32 разряда, как у longWord...
Последний раз редактировалось Developer 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
fir-tree
Сообщений: 10669
Зарегистрирован: 19 июн 2008, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение fir-tree » 25 июн 2008, 15:56

Developer писал(а):Source of the post
1) Каждое действительное десятичное число, представленное в формате c плавающей точкой, можно отображать в виде записи c пятью полями, например, такой:
- первое поле содержит знак числа;
- во втором поле записана целая часть числа (один символ);
- третье поле содержит строку символов дробной части числа;
- в четвёртом поле хранится знак показателя степени по основанию 10;
- пятое поле содержит величину показателя степени (строку символов).

Выгоднее всё-таки числа нормализовать, чтобы запятая стояла перед первой значащей цифрой, a не после неё. Писать вычисления проще: не нужно первую цифру как особый случай обрабатывать.
Последний раз редактировалось fir-tree 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Developer
Сообщений: 6978
Зарегистрирован: 05 сен 2006, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Developer » 26 июн 2008, 07:18

Согласен...
Последний раз редактировалось Developer 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

minzastro
Сообщений: 4
Зарегистрирован: 29 июн 2008, 21:00

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение minzastro » 30 июн 2008, 09:54

Добрый день.
Почитал тему. Любопытственно.
По лености не буду повторять работу, проделанную Девелопером.
Я не спорю, что универсальные программы имеют свои недостатки (в первую очередь, пожалуй, быстродействие - за универсальность надо платить). Ho написать программу, которая бы ВСЕГДА (a не в одном конкретном рассматриваемом случае) могла бы определить, a не нет ли в решении ошибок, связанных c ошибками округления и тому подобным - насколько мне известно - невозможно.
И уж тем более - "на коленке" повторять тысячу раз уже написанные модули для работы c "длинными" числами, и уж тем более - реализовывать их через строки - бессмысленное занятие. Если только Вы не суперпрограммисты и математики, способные предложить реально более быстрые алгоритмы работы c такими числами.
Последний раз редактировалось minzastro 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test

Arven
Сообщений: 642
Зарегистрирован: 09 ноя 2007, 01:31

Алгоритмизация и решение системы линейных уравнений на ЭВМ

Сообщение Arven » 30 июн 2008, 10:10

minzastro писал(а):Source of the post Ho написать программу, которая бы ВСЕГДА (a не в одном конкретном рассматриваемом случае) могла бы определить, a не нет ли в решении ошибок, связанных c ошибками округления и тому подобным - насколько мне известно - невозможно.
Я, по мере прочтения этой темы тоже пришла к выводу, что это так. Числовой ряд вообще бесконечен, a поэтому -- никакая машина и никакой алгоритм никогда не смогут представить и произвести c ним какие-либо ариф. операции точно.
И уж тем более - "на коленке" повторять тысячу раз уже написанные модули для работы c "длинными" числами, и уж тем более - реализовывать их через строки - бессмысленное занятие. Если только Вы не суперпрограммисты и математики, способные предложить реально более быстрые алгоритмы работы c такими числами.
Мне кажется, больше имеют смысл разработки и доработки алгоритмов, работающих c символьными вычислениями. Te же создатели Mathematici -- действительно, супер-программисты, как-то смогли сделать, чтобы программа выдавала относительно точный численный результат, т.e. нашли золотую середину. Алгоритмы символьных вычислений, имхо, могут реально больше пригодиться, чем погоня за "точными" числами :).
A требовать от компьютера: "Вот вычисли мне огромное число c точностью 100 %" -- это в большинстве случаев просто глупо, потому такое число (даже если представить возможность его получения) просто ни для чего не сможет пригодиться.
Последний раз редактировалось Arven 30 ноя 2019, 10:42, всего редактировалось 1 раз.
Причина: test


Вернуться в «Физика»

Кто сейчас на форуме

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