Как се използват алгоритми

Книгата на американски специалист по системно програмиране е уникална колекция от програмни проблеми от различни области: моделиране, изчислителна точност, обработка на текст, изкуствен интелект, дизайн на компилатор. Повечето от задачите се базират на реални и игрови ситуации.

За всички, които преподават и учат програмиране.

Книга: Скици за програмисти

Как се използват алгоритми?

Да намеря? ще е необходимо да се извършат изчисления съгласно една от формулите, изписани по-рано в този параграф, като се използва серия за арктангенса. Всъщност трябва да се използват две формули за застраховка и след това да се сравняват резултатите малко по малко. Стойността? ще бъде общата начална част на тези два резултата.

Все още е открит въпросът как с помощта на алгоритми, които работят само с цели числа, да се получат очевидно дробните стойности на членовете на поредицата. Да кажем, че искаме да изчислим i с, да речем, 1000 бита точност. Нека изчислим тогава 2 1000 ?, умножавайки всички числители по 2 1000. Тази процедура също така прави всички делими много повече делители (както е предложено по-горе) и ви позволява да спрете изчисленията, когато факторите станат нула.

Сега нека да изберем (не непременно най-добрите) серии за изчисления, да речем

? = 16 arctg (1/5)? 4 arctg (1/239).

Всъщност ще изчислим 2 1000, така че бихме искали да изчислим 2 1000 16 арктан (1/5). Първият член на съответния ред ще бъде 2 1000 · 16/5; нека го наречем a1 (имайте предвид, че a1 се добавя към сумата). Сега, за да получим следващия член ai + 1 от ai, разделете a1 на 5 · 5 · (2i? 1) [34]. Ако ai беше добавен към сумата, тогава изваждаме ai + 1 от сумата, ако ai беше изваден, добавяме ai + i. Ще разделим a1 на 5 5 (2i? 1). Ако ai беше добавен към сумата, тогава изчисленията приключват, когато условията на двете серии станат нула. В резултат на това получаваме около хиляда бита от числото ?. Резултатът, разбира се, ще трябва да бъде преобразуван в десетична система.

Предмет. Напишете програми, които прилагат алгоритмите за умножение и деление, описани по-горе, и всякакви подпрограми на услуги, от които се нуждаят. Използвайте ги, за да изчислите i с висока точност, като използвате една от написаните серии. Уверете се, че вашите програми не са твърде тясно обвързани с изчисленията ?; библиотека от програми за високо прецизни изчисления може да бъде полезна и за други задачи. Трябва да е възможно да се увеличи точността на броене, без да се променят програмите, а само чрез разширяване на паметта за резултати. Резултатът трябва да включва статистически данни за използването на всяка програма, за броя изпълнения на всяка стъпка от двата централни алгоритма и за използването на паметта. Събирането на тази информация ще бъде много евтино в сравнение с цялата работа.

Инструкции за изпълнителя. Тази скица е дълга и трудна. Не на последно място роля тук играе фактът, че двата централни алгоритма трябва да се доверят до известна степен. Въпреки това, както често се случва при реални проблеми, основният проблем не е кодирането на програмата, а изборът на структури от данни. Как да представим дълги числа? Нотацията [m, u] предполага, че всяко дълго число е представено с двойка аргументи дължина и стойност. Част дължина лесен за изпълнение, но стойност очевидно е с променлива дължина и би било трудно да се съхранява директно в паметта. Затова ще го направим стойност указател към много дълъг вектор от битове; тогава всяка двойка ще има фиксиран размер. Векторът, с който разполагаме, обаче не е толкова дълъг, че да си позволим да използваме всяка негова част само веднъж. По този начин е необходима програма за събиране на ненужна памет. Сега всъщност описахме традиционната схема поставяне на вериги.