5
votes
In general, in a string of multiplication is it better to multiply the big numbers or the small numbers first?
If the numbers and the product are all "small" (magnitude less than $2^{63}$); the order doesn't matter at all; the multiplication will take time linear in the number of factors as it simply ...
- 47.9k
4
votes
Calculate $ \sum_{k=1}^{n} k\cdot\varphi(k) $
This equality might help a bit:
$$\sum_{k=1}^{n} k\cdot \varphi(k) \ \ = \ \ \sum_{d \le n}{\mu(d)\cdot d \cdot S\left(\left[\frac{n}{d}\right]\right)}, \tag{1}$$
where $S(k)$ is the sum of the first $...
- 329
4
votes
Accepted
Fastest algorithm to compute the square of a number
If you could compute squares quickly then you could compute products quickly since
$$
ab = \frac{(a+b)^2 - a^2 -b^2}{2} ,
$$
- 86.4k
3
votes
In general, in a string of multiplication is it better to multiply the big numbers or the small numbers first?
I'm considering only the number of multiplication steps, because addition has a negligible time-complexity compared to multiplication.
The order in which you multiply the numbers doesn't affect the ...
- 734
3
votes
Accepted
Treatment of P and NP as sets in ZFC/NBG?
If we restrict to a fixed (finite) alphabet at the outset - say, we look at all languages over (= sets of strings formed from) the alphabet $\{0,1\}$ - then complexity classes are sets without further ...
- 229k
2
votes
Is One Way TSP NP-complete?
Here is a self-contained proof for the NP-completeness of one-way TSP.
We can reduce normal (closed) TSP to one-way (open) TSP by solving $\binom n2$ one-way TSP instances, each corresponding to a ...
- 100k
2
votes
Accepted
Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $
$$f(x)=\sum_{k\le x} k \mu(k), \qquad \sum_{d\le x} d f(x/d)=1$$
It gives
$$\qquad \sum_{d=1} d f(x/d) + \sum_{2\le d \le \sqrt x} d f(x/d) + \sum_{\sqrt x \lt d\le x} d f(x/d) =1$$
When $d \in (\...
- 75.8k
2
votes
Calculate $ \sum_{k=1}^{n} k\cdot\varphi(k) $
Found more powerful way of arranging,
let $F(x)=\sum_{k \le x} k\cdot\varphi(k)$
$$ \sum_{i \le x} i \cdot F(x/i) = x(x+1)(2x+1)/6$$
$$ \implies F(x) = x(x+1)(2x+1)/6 \ - \sum_{2 \le i \le x} i \cdot ...
- 451
1
vote
The concepts of P, NP and NP_complete problems for the dummies
The slides in this link look quite reasonable as a very short and gentle introduction:
https://user.it.uu.se/~justin/Assets/Teaching/AD2/Slides/34-PversusNP.pdf
Short approximate answers to your ...
- 8,055
1
vote
In general, in a string of multiplication is it better to multiply the big numbers or the small numbers first?
We can assume that every single word multiplication takes some constant time, and that we need some algorithm to multiply n word by m word numbers. Now the answer depends on how fast this n by m word ...
- 8,724
1
vote
Is non-convex optimisation really in NP class?
NP problems are decision problems, so an optimization problem would need to be restated as a decision problem. Instead of asking what value of $x$ minimizes a function, you would ask if there is a ...
- 1,821
1
vote
Accepted
What is the complexity of global solution of a nonlinear system?
In the worst case, $F_j=0$ for all $j$, and then there are at least $2^n$ roots. Obviously any method to print all roots must take time at least equal to the number of roots, so this proves that the ...
- 2,824
Only top scored, non community-wiki answers of a minimum length are eligible