This is to announce a new version of an electronic preprint concerning instruction sequences. The preprint “Instruction Sequence Expressions for the Karatsuba Multiplication Algorithm” has now been updated (arXiv:1312.1529v2 [cs.PL]). In this preprint, we provide mathematically precise alternatives to the natural language and pseudo code descriptions of the long multiplication algorithm and the Karatsuba multiplication algorithm and establish among other things that the instruction sequence expressing the latter algorithm is shorter than the instruction sequence expressing the former algorithm only if the length of the bit strings involved is greater than 256.

Recent Posts
Categories
Tags
 algorithm efficiency
 algorithmic equivalence
 asserted program
 asserted singlepass instruction sequence
 auxiliary datum
 axiom system
 basic thread algebra
 behavioural congruence
 bit string function
 Boolean function family
 Boolean register
 completeness
 completeness in the sense of Cook
 computational complexity
 crossover point
 halting problem
 highlevel programming language
 Hoare logic
 instruction sequence
 instruction sequence congruence
 instruction sequence size
 instruction set
 jump instruction
 Karatsuba multiplication
 long multiplication
 lowlevel programming language
 meadow
 multiplication algorithm
 nonuniform complexity measure
 parity function
 partial correctness
 probabilistic computation
 probabilistic scheduling policy
 program
 program algebra
 program parallelization
 program size
 singlepass instruction sequence
 sizebounded functional completeness
 soundness
 structural congruence
 thread
 thread algebra
 virus detection
Archives
 November 2017 (1)
 June 2017 (1)
 February 2017 (1)
 January 2017 (1)
 October 2016 (1)
 July 2016 (2)
 June 2016 (2)
 January 2016 (1)
Links