On Machine Synthesis of Some Sequential Programs

A. B. Frolov , A. M. Vinnikov , e-mail: abfrolov@mail.ru

Two methods of automatic generation of sequential programs for multiplication of multidigit numbers using Karatsuba algorithm are discussed. They based on two recursive implementation of Karatsuba algorithm. Analogous approach is described in respect to synthesis of programs for multiplication of high degrees polynomials over finite fields. There is shown the method of comparison of synthesis results to proof the correctness of programs used for their producing. The complexity of those sequential programs is estimated.

Keywords: programming automation, machine synthesis of programs, linear program, multiplication of multi-digit numbers, multiplication of polynomials over finite fields decomposition schema, Karatsuba method, recursion in depth, recursion in width, correctness of programs, complexity estimation

pp. 24–30