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 $...
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 ...
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 ...
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 ...
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