MHB Test whether the integer is a prime

[evinda]

Yep. (Nod)

We could calculate $a$ directly with $a=\sqrtn$.
Or we could calculate the upper bound for $a$ by using the smallest value of $b$ giving us $\sqrt n$.
But those are difficult to calculate with an integer algorithm.
So instead we should probably pick $n$ as upper bound so that we need $\log_2 n$ bisections. (Thinking)

I have thought of the following algorithm:

Algorithm:
k=-1;
b=2;
while ((b<=logn) and (k=-1)){
         k=binarysearch(b,n);
         b=b+1;
}
if (k!=-1) printf("n=%d^%d",k,b);

int binarysearch(int b, int n){
 int low=2;
 int high=n;
 while (low<high){
          int mid=low+floor((high-low)/2);
          if (mid^b==n) return mid;
          else if (mid^b<n) low=mid+1;
          else high=mid-1;
 }
 return -1;
}

Is the algorithm I have written right? But don't we need for the exponentiation time $O((\log{n})^3)$ ?
So will the number of arithmetic operations be greater as desired? (Thinking)

 

[I like Serena]

Is the algorithm I have written right? But don't we need for the exponentiation time $O((\log{n})^3)$ ?
So will the number of arithmetic operations be greater as desired? (Thinking)

It looks correct.
Can't we improve it by starting the next iteration with a new upper bound from the previous iteration? (Wondering)

 

[evinda]

Can't we improve it by starting the next iteration with a new upper bound from the previous iteration? (Wondering)

You mean a new upper bound for $b$ ? How can we find it? (Thinking)

 

[I like Serena]

You mean a new upper bound for $b$ ? How can we find it? (Thinking)

No, a new upper bound for $k$ for the next $b$. (Shake)
Suppose we found that for a certain $b$ we have $k^b<n$ and $(k+1)^b>n$.
Let the next $b$ be $b'=b+1$.
Now we want to see if we can find a corresponding $k'$ such that $n=(k')^{b'}$.
Don't we have that $k' \le k$? (Wondering)

 

[evinda]

No, a new upper bound for $k$ for the next $b$. (Shake)
Suppose we found that for a certain $b$ we have $k^b<n$ and $(k+1)^b>n$.
Let the next $b$ be $b'=b+1$.
Now we want to see if we can find a corresponding $k'$ such that $n=(k')^{b'}$.
Don't we have that $k' \le k$? (Wondering)

Yes, right... (Nod) So does the function binarysearch have to return the value mid for which $mid^b<n$ and $(mid+1)^b>n$ , besides the -1, that indicates that we haven't found a $k$ such that $k^b=n$? So do we have to use pointers at this function?
Or could we do this somehow else? (Thinking)

 

[I like Serena]

In c we can either pass a pointer to return an additional value (an output parameter), or we can return a structure with the values.
In this case i recommend passing a pointer as input-output parameter to track the upper bound. (Thinking)

 

[evinda]

In c we can either pass a pointer to return an additional value (an output parameter), or we can return a structure with the values.
In this case i recommend passing a pointer as input-output parameter to track the upper bound. (Thinking)

I also took a look at the algorithm mentioned in my notes. The algorithm is the following:

View attachment 7608

It says the following about it:View attachment 7609

At the lemma it says that the algorithm makes $O((\log{n})^2 \log{\log{n}})$ multiplications of numbers from $\{1, \dots,n\}$. How do we deduce this? (Thinking)

 

[I like Serena]

At the lemma it says that the algorithm makes $O((\log{n})^2 \log{\log{n}})$ multiplications of numbers from $\{1, \dots,n\}$. How do we deduce this? (Thinking)

How many times does the outer loop run?
The inner loop?
And what is the complexity of fast exponentiation? (Wondering)

 

[evinda]

How many times does the outer loop run?
The inner loop?

The outer loop runs $O(\log{n})$ times. Since with the inner loop we carry out a binary search, it is executed $O(\log{n})$ times, too. Right?

And what is the complexity of fast exponentiation? (Wondering)

For the computation of $m^b$, it is required time $O(\log^3{b})$ using fast exponentiation, right? (Thinking)

 

[I like Serena]

The outer loop runs $O(\log{n})$ times. Since with the inner loop we carry out a binary search, it is executed $O(\log{n})$ times, too. Right?

Yep. (Nod)

For the computation of $m^b$, it is required time $O(\log^3{b})$ using fast exponentiation, right?

Isn't the fast exponentiation $O(\log{b})$?
And we have $b=O(\log n)$ don't we? (Wondering)

 

[evinda]

Isn't the fast exponentiation $O(\log{b})$?

How is it justified that the fast exponentiation is $O(\log{b})$?

And we have $b=O(\log n)$ don't we? (Wondering)

Yes. (Smile)

 

[I like Serena]

How is it justified that the fast exponentiation is $O(\log{b})$?

Isn't the computational complexity of calculating $a^n$ with fast exponentiation:
$$\begin{aligned}g(n)&=\begin{cases}
0, & n=1\\
g\left(\frac{n}{2}\right )+1, & n \text{ even } \\
g(n-1)+1, & n \text{ odd}>1
\end{cases} \\
&=\begin{cases}
0, & n=1\\
g\left(\frac{n}{2} \right )+1, & n \text{ even } \\
g(\frac{n-1}2)+1 + 1, & n \text{ odd}>1
\end{cases} \\
&=\begin{cases}
0, & n=1\\
g\left(\lfloor\frac{n}{2}\rfloor \right )+O(1), & n >1
\end{cases} \\
&= O(\log n)
\end{aligned}$$
(Wondering)

 

[evinda]

Isn't the computational complexity of calculating $a^n$ with fast exponentiation:
$$\begin{aligned}g(n)&=\begin{cases}
0, & n=1\\
g\left(\frac{n}{2}\right )+1, & n \text{ even } \\
g(n-1)+1, & n \text{ odd}>1
\end{cases} \\
&=\begin{cases}
0, & n=1\\
g\left(\frac{n}{2} \right )+1, & n \text{ even } \\
g(\frac{n-1}2)+1 + 1, & n \text{ odd}>1
\end{cases} \\
&=\begin{cases}
0, & n=1\\
g\left(\lfloor\frac{n}{2}\rfloor \right )+O(1), & n >1
\end{cases} \\
&= O(\log n)
\end{aligned}$$
(Wondering)

Why is it plus $1$ at the last two cases?

$$g(n)=\begin{cases}
0, n=1\\
g\left(\frac{n}{2}\right )+1, n \text{ even } \\
g(n-1)+1, n \text{ odd}>1
\end{cases}$$

 

[I like Serena]

Why is it plus $1$ at the last two cases?

$$g(n)=\begin{cases}
0, n=1\\
g\left(\frac{n}{2}\right )+1, n \text{ even } \\
g(n-1)+1, n \text{ odd}>1
\end{cases}$$

We have $a^{2k}=(a^k)^2$ respectively $a^{2k+1}=(a^{2k})\cdot a$, and each takes 1 multiplication. (Thinking)

 

[evinda]

We have $a^{2k}=(a^k)^2$ respectively $a^{2k+1}=(a^{2k})\cdot a$, and each takes 1 multiplication. (Thinking)

I see... So the computational complexity is the number of multiplications done?
It differs from the time complexity, right? (Thinking)

Furthermore, it says that the number $\lceil \log{n} \rceil$ may be calculated in $O(\log{n})$ arithmetic operations (by repeated halving).
How do we calculate $\lceil \log{n} \rceil$ by repeated halving? (Thinking)

 

[I like Serena]

I see... So the computational complexity is the number of multiplications done?
It differs from the time complexity, right?

It depends on how we measure time complexity.
Typically this is the number of multiplications/divisions and (possibly separately) the number of additions/subtractions.
Either way, we can lump it all into one big number with the $O$ operator.
So instead of adding $1\text{ multiplication}$, we might add $O(1)$ to eliminate the type of operation. (Nerd)

Furthermore, it says that the number $\lceil \log{n} \rceil$ may be calculated in $O(\log{n})$ arithmetic operations (by repeated halving).
How do we calculate $\lceil \log{n} \rceil$ by repeated halving?

If we want to know what $\log_2 n$ is, we can simply count the number of bits can't we? (Wondering)

 

[evinda]

It depends on how we measure time complexity.
Typically this is the number of multiplications/divisions and (possibly separately) the number of additions/subtractions.
Either way, we can lump it all into one big number with the $O$ operator.
So instead of adding $1\text{ multiplication}$, we might add $O(1)$ to eliminate the type of operation. (Nerd)

I thought that at the time complexity we usually multiply the number of arithmetic operations by the corresponding time needed... (Thinking)

If we want to know what $\log_2 n$ is, we can simply count the number of bits can't we? (Wondering)

How do we count the number of bits? (Thinking)

 

[I like Serena]

I thought that at the time complexity we usually multiply the number of arithmetic operations by the corresponding time needed...

As far as I know, time complexity is an abstract measure, which can be anything, as long is it's (more or less) related to time.
And saying it's $O(f(n))$ says that it's less then some constant times $f(n)$, which covers any amount of time that a multiplication or addition (that is presumed to be more or less constant) may need. (Nerd)

How do we count the number of bits?

Don't we usually already have a bit representation of $n$?
Either way, even counting bits is effectively the same as repeated halving, which is $O(\log n)$. (Thinking)

 

[evinda]

As far as I know, time complexity is an abstract measure, which can be anything, as long is it's (more or less) related to time.
And saying it's $O(f(n))$ says that it's less then some constant times $f(n)$, which covers any amount of time that a multiplication or addition (that is presumed to be more or less constant) may need. (Nerd)

So we could consider that one multiplication of some integers $a,b$ takes time $O(1)$ or that it takes time $O(\log^2{n})$, right?

Don't we usually already have a bit representation of $n$?
Either way, even counting bits is effectively the same as repeated halving, which is $O(\log n)$. (Thinking)

Ok. But how can we find $\lceil \log{n}\rceil$ by repeated halving? (Thinking)

 

[I like Serena]

So we could consider that one multiplication of some integers $a,b$ takes time $O(1)$ or that it takes time $O(\log^2{n})$, right?

Indeed. (Nod)

Ok. But how can we find $\lceil \log{n}\rceil$ by repeated halving? (Thinking)

How about:
$$
\textbf{Algorithm ILSe.1 (Count Bits)} \\
\textrm{INPUT: Integer }n \ge 0 \\
\begin{array}{rl}
1.& k \leftarrow 0\ ; \\
2.& \textbf{while }n \ne 0 \\
3.& \quad n \leftarrow \lfloor \frac n2 \rfloor\ ; \\
4.& \quad k \leftarrow k+1\ ; \\
5.& \textbf{return } k\ ; \\
\end{array}$$
(Wondering)

 

[evinda]

How about:
$$
\textbf{Algorithm ILSe.1 (Count Bits)} \\
\textrm{INPUT: Integer }n \ge 0 \\
\begin{array}{rl}
1.& k \leftarrow 0\ ; \\
2.& \textbf{while }n \ne 0 \\
3.& \quad n \leftarrow \lfloor \frac n2 \rfloor\ ; \\
4.& \quad k \leftarrow k+1\ ; \\
5.& \textbf{return } k\ ; \\
\end{array}$$
(Wondering)

Nice... (Smile) The algorithm runs as long as $\frac{n}{2^i}\geq 1 \Rightarrow n \geq 2^i \Rightarrow i \leq \log{n}$.

So the time complexity of the algorithm is $O(i)=O(\log{n})$. Right? (Thinking)

 

[I like Serena]

Nice... (Smile) The algorithm runs as long as $\frac{n}{2^i}\geq 1 \Rightarrow n \geq 2^i \Rightarrow i \leq \log{n}$.

Happy that you like it. (Happy)

So the time complexity of the algorithm is $O(i)=O(\log{n})$. Right?

Yup. (Nod)

 

[evinda]

Happy that you like it. (Happy)
Yup. (Nod)

(Happy)

I have also a question for the time required for testing $r$. According to my notes:

View attachment 7611

First of all, how do we deduce that the total cost for line $4$ is $O(\rho(n))$ ?

The Sieve of Eratosthenes algorithm is the following:View attachment 7612

Why do we check what happens when $r$ gets the value $2^i+1$ for some $i$ ? Could you explain it to me? (Thinking)

 

[I like Serena]

I have also a question for the time required for testing $r$. According to my notes:

First of all, how do we deduce that the total cost for line $4$ is $O(\rho(n))$ ?

Isn't line 4 executed $\rho(n)$ times, while the cost of one execution is $1\text{ division} = O(1)$? (Wondering)

The Sieve of Eratosthenes algorithm is the following:

Why do we check what happens when $r$ gets the value $2^i+1$ for some $i$ ? Could you explain it to me?

I believe it's to reuse the same table for a number of iterations of $r$.
When $r$ runs out of the table, the table size is doubled and recalculated for the next series of iterations of $r$. (Thinking)

 

[evinda]

Isn't line 4 executed $\rho(n)$ times, while the cost of one execution is $1\text{ division} = O(1)$? (Wondering)

Oh yes, right... (Nod)

I believe it's to reuse the same table for a number of iterations of $r$.
When $r$ runs out of the table, the table size is doubled and recalculated for the next series of iterations of $r$. (Thinking)

But why do we check only what happens when $r$ is of the form $2^{i}+1$ although not every prime can be written in this form?

Also if $r=2^i+1$ for some $i$ don't we get a table of size $2^{\lceil \log{(2^{i}+1)}\rceil}-1$ ? Or am I wrong?

 

[I like Serena]

But why do we check only what happens when $r$ is of the form $2^{i}+1$ although not every prime can be written in this form?

Also if $r=2^i+1$ for some $i$ don't we get a table of size $2^{\lceil \log{(2^{i}+1)}\rceil}-1$ ? Or am I wrong?

The size of the table is not related to primes.
Since we double the table size each time, we have $2^i$ entries in there at all times.
And when $r$ becomes $2^i+1$ it refers to an entry in the table that is not there yet, which is when the table gets resized, after which it will have $2^{i+1}$ entries.
Now the main algorithm can continue running $r$ from $2^i+1$ up to $2^{i+1}$ before we run out of the table again. (Thinking)

 

[evinda]

The size of the table is not related to primes.
Since we double the table size each time, we have $2^i$ entries in there at all times.

Why do we double the table size each time? I haven't understood it... (Worried)

 

[I like Serena]

Why do we double the table size each time? I haven't understood it... (Worried)

The Sieve of Erathosthenes does not find individual primes, but instead finds all primes in the range that we specify.
The complexity to figure out if some number $m$ is prime has the exact same complexity as finding all primes up to $m$.
So instead of rerunning the sieve for every $r$, we run it once for a range, and then iterate $r$ through that range.
And afterwards we rerun the sieve on a larger range.

It's an arbitrary decision to double the table every time.
We could also triple it, or each time add 1000 entries to it, or use yet some other scheme to grow the table.
However, we do not want to run the sieve for the full range up to $n$, since that is too computationally expensive. (Thinking)

 

[evinda]

The Sieve of Erathosthenes does not find individual primes, but instead finds all primes in the range that we specify.
The complexity to figure out if some number $m$ is prime has the exact same complexity as finding all primes up to $m$.
So instead of rerunning the sieve for every $r$, we run it once for a range, and then iterate $r$ through that range.
And afterwards we rerun the sieve on a larger range.

It's an arbitrary decision to double the table every time.
We could also triple it, or each time add 1000 entries to it, or use yet some other scheme to grow the table.
However, we do not want to run the sieve for the full range up to $n$, since that is too computationally expensive. (Thinking)

Ok.

The size of the table is not related to primes.
Since we double the table size each time, we have $2^i$ entries in there at all times.
And when $r$ becomes $2^i+1$ it refers to an entry in the table that is not there yet, which is when the table gets resized, after which it will have $2^{i+1}$ entries.
Now the main algorithm can continue running $r$ from $2^i+1$ up to $2^{i+1}$ before we run out of the table again. (Thinking)

So at the first execution of the Sieve of Erathosthenes we will get the table $m[2 \dots 2^{i}+1]$ so that it contains $2^{i}$ entries? (Thinking)
But if so then $m[2^{i}+1]$ will have got an entry, or am I wrong? (Thinking)

 

[I like Serena]

So at the first execution of the Sieve of Erathosthenes we will get the table $m[2 \dots 2^{i}+1]$ so that it contains $2^{i}$ entries?
But if so then $m[2^{i}+1]$ will have got an entry, or am I wrong?

I think we're only talking about the upper bound instead of the actual size of the table.
In the first iteration we will have $m[2 \dots 2^{1}]$, then $m[2 \dots 2^{2}]$, and so on.
Generally we have $m[2 \dots 2^{i}]$, meaning that $2^i+1$ is not in the table. (Thinking)