Dr. K. L. Metlov (dr_klm) wrote,
Dr. K. L. Metlov
dr_klm

Non-adjacent form (NAF) на J

Написал вот с подачи Роджера заметку о NAF в J Wiki. Об этом деле, помню, мы с Raul-ем Miller-ом поломали копья в J Forum-е, когда он меня пытался убедить, что для эффективной реализации нужно использовать конечные автоматы (глагол ;: в языке J).

Интересно сравнить алгоритмы вычисления NAF из Wikipedia (modified Booth scheme, repeated division) и эквивалентный однострочник на J:
NAF=: }:@(-/)@#:@(_1 _3&*)
Однострочник в J Wiki пришлось (по просьбам товарищей) усложнить. Он поддерживает массивы (для реализации умножения на скаляр в Elliptic Curve Cryptography это не очень нужно) и включает в себя (заодно) определение обратного глагола.
Tags: j
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments