Възможно ли е да се изработи алгоритъм за изваждане, който първо не сравнява входовете? - алгоритъм, език-агностик, изваждане

Очевидно всеки компетентен програмен език имавградено изваждане. Обаче, кажете, че трябва да въведете алгоритъм за изваждане по избор (да кажем, че трябва да се справяме с много големи числа). Ако използвате метода за заемане, първо трябва да сравните входовете, за да определите дали резултатът ще бъде отрицателен и ако е така, ще превключите реда на изваждането. Аз съм любопитен, ако е възможно да се напише алгоритъм, който не се нуждае от това сравняване / операнд суап?

Освен това би могъл такъв алгоритъм да бъде по-ефективен, отколкото да се сравнява първо, което в най-лошия случай би трябвало да сравнява всяка стойност на мястото?

* Зная, че може да се използват допълнения, но това ограничава размера на позволените входове (при условие, че има ограничен размер на представяне).

Отговори:

Ако внедрявате bignums, можете да комбинирате сравнението и изваждането, така че да погледнете само всеки от тях "Крайник" веднъж, с изключение на едно. (Думата "крайник" идва от библиотеката "Гну ПМ", но се използва и другаде, за да означава същото нещо.)

Първо, сканирате от най-големия край на по-дългатадокато не намерите ненулев крайник или ще достигнете дължината на по-малкия брой. В първия случай вие знаете, че по-дългият брой е по-голям и знаете и позицията на най-значимия му крайник. (Ако сте приели конвенцията, че номерата винаги имат най-значителен ненулев край, тогава можете да пропуснете тази стъпка.)

Представете си, че вече не сте доказали колкото по-дългономерът е по-голям, така че знаете, че сте на едно и също място и в двата номера. Продължете да сканирате и двата номера, докато не откриете разлика. В този момент знаете кой номер е по-голям и знаете също и позицията на най-значимия крайник на по-голямото число.

Значи сега знаете кой номер е по-голям, и виеможе да направи нормалния алгоритъм за заемане от ниските крайни стойности на номерата, спирайки, когато стигнете до крайника за висок ред, който сте идентифицирали по-рано.

Тъй като двата сканирания спират на едно и също място, не се вглеждате в крайниците повече от веднъж, изваждате крайника, който спира първото сканиране.

Независимо дали всъщност си струва да приложите тази хак, това е нещо, което ще трябва да решите. Възможно е усложнението да не бъде уредено. Но е възможен.