Home

Not insisting this would have been the only reason

After <head></head>, when and why does Google analytics apply to target_blank? (does iframe matter)

If main.html has the java script, when does the new window after how many clicks still have gotten the java script applying to each file, e.g., screenshot of email, or back in 2019, between Google Analytics and individual files on AWS.

Leaving aside the consecutive visits part on Google Analytics, the reason I can tell whether someone scrolled down to a specific line was, at least, back in 2019-21, the option on img src that only loads the image, of all files linked in that html file, when it actually shows on screen. In the IP log, only the downloaded images are logged.

Below is the body part of the html on suehyunsblog.net in summer 2021.

<body>

Please email <a href="mailto:skwon@alumni.princeton.edu" style="text-decoration:none">skwon@alumni.princeton.edu</a> instead of suehyun.kwon@gmail.com and email me if you would like any content to be taken down. This website logs every IP address each file is accessed from. The PDF version of the CV without papers is <a href="cv_2021.pdf">here</a>.

Among the proofs I posted earlier, these two seem correct, and I revised the factorization algorithm which starts in the next paragraph. Travelling salesman needs to be rewritten, and the computational complexity of graph isomorphism seems correct to me, but referees told me I need to explain the algorithm in more detail.

I also posted revised versions for these two in October 2019, which are still on the other domain.

<a href="erdos-faber-lovasz-latest.pdf" style="text-decoration:none">Erdos-Faber-Lovasz (1972)</a>

<a href="coloring-latest.pdf" style="text-decoration:none">Four-color Theorem</a>

<a href="factorization-latest.pdf" style="text-decoration:none">This</a> was the draft on computational complexity of factorization from October 2019, and <a href="http://suehyunsblog.net/factorization.pdf" style="text-decoration:none">this</a> is the revised version from March 19, 2021. It contains the update in binary, instead of the decimals, and I wrote a bit more on relevant calculations for multiplication and division <a href="intro.html#factorization_update" target="main" style="text-decoration:none">below</a>.

Apr 3, 2020

I was trying to code the factorization algorithm in <a href="factorization-latest.pdf" style="text-decoration:none">Computational Complexity of Factorization (Oct 2019)</a> in C++. As it turns out, there is no data type in C big enough for integers I wanted to factor, and I haven't thought through whether one should enter the integer as an array of Booleans in such cases. This is roughly how I was writing it out.

Key ideas are (i) multiplication and division algorithms can be improved by using mod p, which is already written out in the paper and (ii) it can be improved further if all integers are treated in binary, i.e., p=2.

divbasic function shows how these ideas can be performed in a code. This function considers dividing integer n by integer d, only if the numbers of digits of two integers in binary differ by at most one. If n has only one more digit than d, then n/d (or n/d-1) can be 11 in binary, 3 in the usual way of counting integers, only if there are no consecutive 1's in d before having at least two preceding 0's. Therefore, by checking whether there are two consecutive 1's in d, one can narrow down the factor to 10 or 1 qucickly, and if the floor of n/d is 10, then one just needs to add 0 at the end of d to get n, or add 1 afterwards.

This way of counting seems to make the algorithm polynomial, but Shor's algorithm is polynomial only with quantum computers and not with classical computers. I then realized C doesn't have the data type for the integers I wanted to factor, but if one were to enter the data in binary anyway, then it seems polynomial to me, and the problem is either the sieving method or the way division is performed.

Dec 8

This post is a follow up on the one from April 3. I only showed that the algorithm for factorizing integers is in polynomial time in decimal if and only if it is in polynomial time in binary in <a href="factorization-latest.pdf" style="text-decoration:none">Computational Complexity of Factorization (Oct 2019)</a>. I didn't write out in complete detail about how the computational complexity for addition adds up from one unit for adding two digits in binary. I think the argument below shows that the algorithm is in polynomial time in binary, and further improvements can be done at two specific points.

The syntax here is in Matlab, and I haven't checked if there is any unnecessary units consumed in loading binary digits from a given integer when it is stored in a specific datatype.

If the goal is to find all prime numbers weakly less than N and at the same time check whether each prime number is a factor of N, one can do the following.

M(1,N)=0; % initialize a vector of length N

% M(1,i)=0 if i is prime and 1 otherwise

M(1,1)=1;

k= % #1: take the rounding up of sqrt(N) to the next binary digit, the number of digits of sqrt(N) is roughly one half of the number of digits of N

for i=2:k

if M(1,i)=0

j=2*i; % in binary, just adds 0 at the end

while j<=N

M(1,j)=1; % #2: one can store j if j=N to find all factors of N

j=j+i;

end

end

To show that the only places for improvement are #1 and #2, one should note that each number needs to be loaded at least once to check the corresponding M(1,i). If some j is loaded more than once to be marked as 1, the coefficient on i has a factor smaller than i, and loading j as it is requires adding i to the prev multiple and loading M(1,j) once to check on the coefficient. One has to load M(1,factor) at least once. If the multiple of i needs to be computed for a bigger coefficient anyway, then either the multiplication should be performed differently. Or if added throughout anyway, then it doesn't save anything. Therefore, the algorithm can be improved only if bigger multiples of i are performed as multiplication and not by adding i again and again.

Specifically, the operations or the parameters that can be improved upon are k and the routine inside the while, and for the routine inside the while, the specific points where it can be improved upon are

(1) which is faster between i+i+...+i (k times) and i*k,

(2) N/i vs. i+i+...+i ((N-sqrt(N))/i times).

Before discussing the improvements, it seems straightforward to count the complexity as it stands, and if one rounds up the squareroot of N to the next binary digit, then it is multiplied by a constant scalar in computational complexity and doesn't change whether the algorithm can be done in polynomial time. Next, the addition inside the while is also done in binary digits, and when two numbers are added, there cannot be more than 1+1+1 at a given digit passing on nothing bigger than 1 to the next digit.

So the question seems to be whether two specific operations can be done faster.

There are actually two more things one can elaborate on, and the questions are

(3) how fast does division need to be to make it faster to try all non-prime numbers instead of finding prime numbers up to sqrt(N) first,

(4) why the algorithm above runs from k to N inside the while loop.

(4) is essentially taken care of by (2), and for (3), if a divides b and b divides N, then by checking b as a multiple of a (and therefore nonprime), it just drops the part of the algorithm for counting multiples of b, since the algorithm does check for multiples of a up to N.

When operations are done in binary, which I think is the case with C, multiplying by 2 adds 0 at the end of the number, and each digit can be only 0 or 1. When looking for a squareroot of N, if the number of digits is 2m, so that the rounding up the number gives you 2^{2m}, the squareroot has m digits. If the number of digits is 2m-1, so that the smallest with the same number of digits is 2^{2m-2}, then the squareroot has m digits. One can start counting the next digit given the number of digits, but I will post more later.

March 23, 2021

Instead of writing a general statement on multiplication and division, I will describe how the factorization algorithm above can be made faster.

When numbers are stored in binary and operations are performed directly on binary digits, each digit can be only 0 or 1, and multiplying by 2 adds 0 at the end of the number.

When looking for the positive square root of N, if the number of digits is 2m, so that the rounding up the number gives you 2^{2m}, the square root has m digits. If the number of digits is 2m-1, so that the smallest with the same number of digits is 2^{2m-2}, then the square root has m digits.

In the factorization algorithm, there is a while loop that adds a given integer i to itself until the sum becomes bigger than another given number N. Adding i to a multiple of itself, in the standard way, takes the last binary digits and adds the two, which is one unit, and proceeds towards the first digits. In the last digit, if two binary digits are both 1, then 1 is passed onto the next step. If at any subsequent point, if 1 is passed on, then adding three numbers takes two units. If at least one of the two binary digits are 1, then 1 is passed onto the next step again. Therefore, the total units of operation for addition cannot be more than twice the number of binary digits in N.

As for comparing the sum to N along the way, since this step only needs to check whether the given multiple of i is bigger than N, one can start by checking whether the given multiple of i has more digits than N. This step has been running at each round of adding i to the sum, and the sum was smaller than N in the previous round of comparison. Therefore, the multiple of i has at most one more digit than N, and comparing the digit prior to the first digit of N for both numbers is enough, which takes one unit of operation. Next, compare the first digit of N to the corresponding digit in the multiple of i. Each digit can be only 0 or 1, and if at any point, the digit in N is different from the corresponding digit in the multiple of i, then it is confirmed which number is bigger, and there is no need to check remaining digits. The total units of operation is at most the number of digits in N plus one, which is at most twice the number of digits of N.

Therefore, the while loop as it is written in the algorithm takes at most four times the number of digits of N, which is linear.

What can be improved upon is that, in this particular instance, it is not just any multiple of i being compared to N or N being divided by any given i to check whether i is a factor of N. Any algorithm that wants to confirm N is a prime number must check whether any natural number weakly less than the square root of N is a prime number if not whether it divides N.

The counting of units above already incorporates this idea in adding i to itself. It starts from the smallest prime number, 2, and the algorithm only runs further with i that is not a multiple of any smaller positive integer, i.e, prime numbers. All multiples of prime i weakly less than N is marked in the while loop, so that each multiple of i, when the for loop gets there, only checks the index M and doesn't consume any unit of operation.

If each positive integer weakly less than the square root of N will be loaded at least once, one can store what is already computed for each integer, and this is where the operations can be made faster.

March 25, 2021

The algorithm as it stands, if the while loop runs up to N, performs inside of the while loop roughly by the sum of the number of distinct prime factors of integers between 2 and N. It is slightly more, since the loop only stops at the smallest multiple of each prime number that is weakly greater than N. For the purpose of counting computational complexity, only the highest order term matters, and a scalar multiple doesn't matter.

In the meantime, if all integers between 2 and the square root of N are accessed once, this is 2^{n/2} for n=floor(log_2 N)+1.

Two points where the algorithm can be improved upon are (1) finding the square root of N, instead of halving the number of binary digits and rounding up to the next digit, and (2) checking whether a given prime number is a factor of N. Without checking whether p divides N, the while loop can run up to the square root of N instead of N. If the while loop only runs up to the square root of N, then the algorithm finds all prime numbers weakly smaller than the square root of N. It still doesn't bring down the computational complexity to 2^{n/2} because at each integer, checking whether it is prime takes more than one unit.

For division, I haven't put what is below together in the context of (2) and haven't checked whether there is something one can further optimize over, given the fact that all prime numbers between 2 and the square root of N must be checked, and all non-prime numbers need to be marked as non-prime.

Given that 2^{p-1}\equiv 1 (mod p), if the binary representation of N is cut at every (p-1) digits and added up together, the residue from dividing N by p doesn't change. 2^k (mod p) passes through 1 to p-1 as k goes from 1 to p-1, but not necessarily in the same order. Since (2^{(p-1)/2})^2\equiv 1 (mod p), 2^{(p-1)/2} has to be -1 (mod p), and one need not compute 2^k from 1 to p-1. It is sufficient to compute and store from 1 to (p-1)/2, then put the minus sign in front of corresponding ones for (p+1)/2 to p-1.

Adding up pieces of (p-1) consecutive digits starting from the last digit takes maximum twice of log N units, which is linear in computational complexity.

Computing 2^k if the products are stored as k goes from 1 to (p-1)/2 requires adding a 0 at the end of the number and storing it (p-1)/2 times.

Given the sum of (p-1) digit pieces, one needs to multiply corresponding coefficients to 2^k before adding them up.

These three steps determine the number of units required to check the residue of N divided by p. In case of p=3, if the binary digits starting the last digit are labelled n_0, n_1, … respectively for 2^0, 2^1, …, it comes down to n_0-n_1+n_2-n_3+...

What needs to be checked here regarding division is that for numbers weakly less than 2^{(p-1)/2}, how many units it takes to divide it by p and the relative gain of dividing by p whenever possible so that the relevant variable stays between 1 and p-1.

March 27, 2021

In the algorithm I posted about since March 19, the algorithm checks all multiples of a given prime number p in the while loop, by adding it to itself then the sum until the sum becomes bigger than the other given number N. N is the integer one wants to factor.

What is below shows that checking whether a prime number p is a factor of N directly can be done in O((log N)^2) or O(n^2) when n is the number of digits of N in binary.

Following up on the post from March 25, the second step of taking mod p of 1,2,2^2,...,2^{p-2} at each step is at most log N to multiply by 2 and again at most 3 log N to take mod p after the multiplication. This is because if 2^k\equiv i mod p, for 0\leq i<p, then 2i<2p, and one needs to subtract p from the product in case 2i\geq p. Therefore, the computational complexity is at most (p-1)*4 log N, and given that one need not deal with 2^k>N even if k<p, p-1 is at most log N, making the whole step O((log N)^2).

From the first step, the sum of two (p-1) digit pieces is never bigger than 2^p, and if the coefficient of 2^{p-1} is 1, one can (i) drop the coefficient of 2^{p-1}, (ii) take the last (p-1) digits, and (iii) add 1 to the sum with the next (p-1) digit piece. This is the same as taking mod p once more, and it doesn't change the first step being O(log N).

Now, in the third step, one can multiply the coefficient for each 2^k, add them up and take mod p once more. Since each coefficient is 0 or 1 if the first step is done as in the previous paragraph, it is equivalent to just adding up 2^k mod p for k's whose coefficient from the first step is 1. Regardless, there are at most log N numbers with at most log N digits to add, and we get O((log N)^2).

Across all three steps, we have O(log N), O((log N)^2) and O((log N)^2), and the sum is O((log N)^2).

A course in number theory and cryptography by Koblitz only seems to have the factorization for m that is not necessarily prime, and my copy of the book is old. I have not checked the recent results yet.

March 29, 2021

In the <a href="http://suehyunsblog.net/factorization.pdf" style="text-decoration:none">pdf</a> file from March 19, I pointed out two places at which the algorithm can be made faster. &num1; is rounding up the square root of N to the next digit, and &num;2 checks whether a given prime p is a factor of N. The division algorithm from March 27 takes O((log N)^2), which is polynomial. If in the algorithm, the while loop runs up to the square root of N instead of N, it saves adding p to the multiple of itself, which is O(log N), (N-sqrt(N))/p times. Given that p is weakly smaller than the square root of N, (N-sqrt(N))/p>=sqrt(N)-1.

The algorithm can be alternatively written as

M(2,N)=0; \&#37 initialize a matrix of size 2 by N

\&#37 M(1,i)=0 if i is prime, -1 a prime factor of N, and 1 otherwise

M(1,1)=1;

k= \&#37 \&num;1: take the rounding up of sqrt(N) to the next binary digit, the number of digits of sqrt(N) is roughly one half of the number of digits of N

ub=N;

for i=2:k

if M(1,i)=0

if mod(ub,i)=0

M(1,i)=-1;

end

while mod(ub,i)=0

ub=ub/i;

M(2,i)=M(2,i)+1; \&#37 \&num;2: M(1,i)=-1 indicates i is a factor of N, and M(2,i) is the exponent on i

end

if ub<k

k=ub;

end

j=2*i; \&#37 in binary, just adds 0 at the end

while j<=k

M(1,j)=1;

j=j+i;

end

end

mod(ub,i) takes the residue of dividing ub by i, when i is a prime number, as in the post from March 27. I also just wrote ub/i, but I meant the division I wrote in that post. As for replacing k with ub, given that k stays fixed until ub becomes smaller than k, if it does, and once it happens, ub is smaller than k until the program ends, it can be done once instead of comparing ub and k with each prime i. However, this comparison is O(log N).

Counting the exact savings in units takes a bit more care, since O(log N) for addition earlier was an upper bound, and multiple rounds of adding some i to itself can still be smaller than log N.

July 9, 2021

I was revising the travelling salesman, and what's below works when the cost of travelling between any pair of cities is given in advance, but it doesn't seem to work if prices are moving and only the distribution of prices are given until they are realized. If the costs are all given in advance, this is what I got.

The travelling-salesman problem with asymmetric costs pertains to finding the minimum-cost path across all (finite number of) n cities when travelling from city i to j costs c_{ij} and the salesman needs to come back to the city he started with. Asymmetric costs allow c_{ij} to be different from c_{ji}, and the salesman must stop at every city once. One needs to compare n! paths if one were to compare every possible path with the given number of cities. The approach I take builds on the observation that for the purpose of finding the minimum cost, one can restrict attention to the sum of n entries from the matrix whose (i,j)-th entry is c_{ij} so that there is only one entry from each column and each row. Since the salesman stops by each city once, for each of the n cities, there is only one city the salesman departs to, and therefore there exists precisely one entry from each row among n entries. Likewise, for each city, there is only one city the salesman arrives from, and therefore there exists one entry in each column among the n entries. If the i-th row and the j-th column are removed after the (i,j)-th entry is chosen, then we are left with an (n-1)x(n-1) matrix and can apply the recursive structure.

Given that there must be exactly one entry from the first row, one can focus on minimizing the sum of the entry from the first row and the minimum cost from the resulting matrix. However, if one only focuses on the first row, one can see that the computational complexity of this algorithm is in the order of

(n-1)x(1+computational complexity with (n-1) cities)+O(n^2)

~ (n-1)x(computational complexity with (n-1) cities)

if it takes more than O(n). (O() actually needs to be in the number of digits of n, not just n, but I will come back to it later) If one were to compute the minimum path for each subjugate matrix every time, then this doesn't help much in lowering O(n!). If one further considers the fact that the first column also corresponds to the same city as the first row and that one can add a direct path from city i to 1 to j to the minimum-cost path from j to i&rt;1, then the computational complexity of the resulting (n-1)x(n-1) matrix is added, not multiplied, to the computational complexity of any operation with the first row and the first column. One should also note that storing any cost that is already computed with a fewer number of cities doesn't add any computational complexity, and it takes about the same whether the salesman comes back to the first city or not since by then the final return cost is the only possible n-th entry.

The cost matrix has M_{ij}=c_{ij} for all pairs of (i,j) except for M_{ii}=0, i=1,...,n.

Definition 1

n cities are denoted by nodes 1,...,n, and the cost of travelling directly from city i to j, different from i, is denoted by c_{ij}.

Definition 2 [Asymmetric costs]

c_{ij} is allowed to be different from c_{ji}, for any distinct i, j<=n.

Definition 3 [Minimum-cost path]

Given k nodes 1,...,k and two distinct nodes i, j<=k , a path from i to j is a bijection f: {1,...,k}\to {1,...,k} such that f(1)=i, f(k)=j and there exists a direct link from f(l) to f(l+1) for all l=1,...,k-1. The path has minimum cost if \sum_{l=1}^{k-1}c_{f(l)f(l+1)}=\min_{g} {\sum_{l=1}^{k-1}c_{g(l)g(l+1)}} among all bijections g:\{1,...,k\}\to\{1,...,k\} such that g(1)=i, g(k)=j.

Denote the set of all minimum-cost paths as \mathcal{P}_{\{1,...,k\}}. The length of a path is the number of cities in the path.

Definition 4 [Minimum-cost cycle]

A cycle through k nodes is a bijection f: {1,...,k}\to {1,...,k} such that there exists a direct link from f(l) to f(l+1) for all l=1,...,k-1 and also from f(k) to f(1). The cycle has minimum cost if c_{f(k)f(1)}+\sum_{l=1}^{k-1}c_{f(l)f(l+1)}=\min_g {c_{g(k)g(1)}+\sum_{l=1}^{k-1}c_{g(l)g(l+1)}} among all bijections g: {1,...,k}\to {1,...,k}.

Denote the set of all minimum-cost cycles as \mathcal{C}_{{1,...,k}}. The length of a cycle is the number of cities in the cycle.

Note that there can be multiple paths with the same minimum cost and multiple cycles with the same minimum cost.

Lemma 1-3 are straightforward, so I didn't put the proofs here.

Lemma 1

Suppose a cycle through k cities has the minimum cost and f is the corresponding bijection. Given distinct i, j<k, denote f(m-1)=j,f(m)=k,f(m+1)=i, allowing for f(0)=f(k) and f(k+1)=f(1). The path from i to j through

{1,...,k-1}, defined by f, has the minimum cost.

Lemma 2

Suppose a path from i to j over k nodes, defined by f, has minimum cost. The cycle defined by the same bijection f has minimum cost conditional on having the segment j\to i. Likewise, given a cycle of minimum cost over k nodes, the same bijection defines a minimum cost path from i to j<= k, i different from j, for each direct link from j to i in the given cycle.

Lemma 3

Suppose a path from i to j over k-1 nodes, defined by f, has minimum cost. The cycle defined by g: {1,...,k}\to {1,...,k}, g(l)=f(l), for all l<k, g(k)=k has minimum cost conditional on having the segment j\to k\to i.

Lemma 3 is the converse of Lemma 1.

I will write up the next lemma with the proof.

</body>

Page updated

Google Sites

Report abuse