Netriwial'nye prakticheskie algoritmy

Odnoj iz naibolee ispol'zuemyh na praktike qwlqetsq zadacha wychisleniq naibol'shego obschego delitelq. V nastoqschee wremq my daem nowuü traktowku ätoj nauchnoj otrasli. Iz istoricheskih istochnikow izwestno, chto grecheskij matematik Ewklid opisal podobnyj iteracionnyj process. V ego original'nom opisanii ispol'zowalas' arifmeticheskaq operaciq "raznost'". Mnogo let spustq, kogda byli razrabotany chislennye metody i osobenno komp'ütery, Knut priwodit komp'üternyj algoritm wychisleniq naibol'shego obschego delitelq s pomosch'ü operacii "ostatok". Bolee bystrye algoritmy mozhno poluchit', kombiniruq dwa podhoda - naprimer, algoritm naimen'shego absolütnogo ostatka, algoritm Stejna, algoritm Harrisa i algoritm Tembhurna-Sate. Nashi issledowaniq pokazywaüt, chto nailuchshie wychislitel'nye rezul'taty daüt predstawlennye w ätoj knige nowye realizacii: algoritma naimen'shego absolütnogo ostatka dlq obychnyh celyh chisel i algoritma Temburna-Sate dlq dlinnyh celyh chisel.