МЕТОДИ ПЕРЕНЕСЕННЯ І ЗАПОЗИЧЕННЯ У ШВИДКОДІЮЧИХ ФІБОНАЧЧІЄВИХ ЛІЧИЛЬНИКАХ

Анотація

У даній статті описано підхід до організації перенесення при лічбі у модифікованій фібоначчієвій системі числення. Даний підхід полягає у тому, що на кожному такті лічби наряду з додаванням одиниці у молодший розряд в залежності від напрямку лічби виконується один із видів фібоначчієвого перетворення (F-перетворення) коду лічильника. Використання FL- та FR‑перетворень дозволяє виконувати перенесення і запозичення ще до того, як виникне переповнення у молодших чи загублення значення у старших розрядах. Це дозволяє уникати ситуацій, при яких за один такт перенесення або запозичення розповсюджуються далі ніж через три розряди. У статті описано модифіковану фібоначчієву систему числення, наведено аналітичні вирази для опису базису і алфавіту та показано, як представляються у ній числа. Наведено аналітичні вирази, що описують FL- та FR‑перетворення. Сформульовано твердження про те, що при виконанні всіх можливих фібоначчієвих перетворень на кожному такті лічби отриманий код буде мати не більше двох сусідніх одиниць. Це дозволяє організувати швидку лічбу за рахунок малого часу розповсюдження перенесення і запозичення.