Yiping Cheng

Yiping Cheng

The traditional Karatsuba algorithm for the multiplication of polynomials and multi-precision integers has a time complexity of $O(n^{1.59})$ and a space complexity of $O(n)$. Roche proposed an improved algorithm with the same $O(n^{1.59})$ time complexity but with a much reduced $O(\log n)$ space complexity. In Roche's paper details were provided for multiplication of polynomials, but not for multi-precision integers. Multi-precision integers differ from polynomials by the presence of carries, which poses difficulties in implementing Roche's scheme in multi-precision integers. This paper provides a detailed solution to these difficulties. Finally, numerical comparisons between the schoolbook, traditional Karatsuba, and space-efficient Karatsuba algorithms are provided.

Yiping Cheng

The backpropagation algorithm for neural networks is widely felt hard to understand, despite the existence of some well-written explanations and/or derivations. This paper provides a new derivation of this algorithm based on the concept of derivative amplification coefficients. First proposed by this author for fully connected cascade networks, this concept is found to well carry over to conventional feedforward neural networks and it paves the way for the use of mathematical induction in establishing a key result that enables backpropagation for derivative amplification coefficients. Then we establish the connection between derivative amplification coefficients and error coefficients (commonly referred to as errors in the literature), and show that the same backpropagation procedure can be used for error coefficients. The entire derivation is thus rigorous, simple, and elegant.