Add to ORKGThe \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least number of 1's required to represent $n$, using only 1's, the addition and multiplication operators, and the parentheses. The running time of the algorithm currently used to compute $f(n)$ is $\Theta(n^{2})$. In this paper we present an algorithm with $\Theta(n^{\log_{2}3})$ as its running time. We also present a proof of the theorem: the largest solutions of $f(m)=3k,\,3k\pm1$ are, respectively, $m=3^{k},\,3^{k}\pm3^{k-1}$.Updated October 23, 201
We present the 2k-ary and the sliding window algorithms for fast exponentiation. We give a precise f...
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] ...
computation. In 3 (dealing with polynomial reciprocals) we use a circuit model with operations in an...
The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least n...
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexit...
Define $||n||$ to be the \emph{complexity} of $n$, which is the smallest number of $1$s needed to wr...
What is an algorithm and what is its complexity? + An algorithm takes Inputs and produces Outputs + ...
AbstractIt has long been observed that certain factorization algorithms provide a way to write the p...
Building on an earlier approach by Isbell and Guy, this short note gives a new, constructive upper b...
Let M(n) denote the bit complexity of multiplying n-bit integers, let ω ∈ (2, 3] be an exponent for ...
A central goal of algorithmic research is to determine how fast computational problems can be solved...
In this article we formalize in Mizar the maximum number of steps taken by some number theoretical a...
AbstractA probabilistic test for equality a=bc for given n-bit integers a,b,c is designed within com...
AbstractBy the complexity KF(Φ) of the formula Φ: (A ⋁ B) ⇒ C we mean the minimal length of a progra...
AbstractThere are many problems in computational geometry for which the best know algorithms take ti...
We present the 2k-ary and the sliding window algorithms for fast exponentiation. We give a precise f...
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] ...
computation. In 3 (dealing with polynomial reciprocals) we use a circuit model with operations in an...
The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least n...
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexit...
Define $||n||$ to be the \emph{complexity} of $n$, which is the smallest number of $1$s needed to wr...
What is an algorithm and what is its complexity? + An algorithm takes Inputs and produces Outputs + ...
AbstractIt has long been observed that certain factorization algorithms provide a way to write the p...
Building on an earlier approach by Isbell and Guy, this short note gives a new, constructive upper b...
Let M(n) denote the bit complexity of multiplying n-bit integers, let ω ∈ (2, 3] be an exponent for ...
A central goal of algorithmic research is to determine how fast computational problems can be solved...
In this article we formalize in Mizar the maximum number of steps taken by some number theoretical a...
AbstractA probabilistic test for equality a=bc for given n-bit integers a,b,c is designed within com...
AbstractBy the complexity KF(Φ) of the formula Φ: (A ⋁ B) ⇒ C we mean the minimal length of a progra...
AbstractThere are many problems in computational geometry for which the best know algorithms take ti...
We present the 2k-ary and the sliding window algorithms for fast exponentiation. We give a precise f...
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] ...
computation. In 3 (dealing with polynomial reciprocals) we use a circuit model with operations in an...