Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Kannan Balasubramanian (Mepco Schlenk Engineering College, India) and M. Rajakani (Mepco Schlenk Engineering College, India)

Copyright: © 2018
|Pages: 12

DOI: 10.4018/978-1-5225-2915-6.ch018

Chapter Preview

TopSuppose I give you a set of integers and I ask you to find a subset of those integers whose product is a square, if one exists. For example, given the set {10, 24, 35, 52, 54, 78}, the product 24×52×78 is 97344 = 312^{2}. The brute-force solution, trying every subset, is too expensive because there are an exponential number of subsets.

Another approach is based on prime factorizations and linear algebra. First, we factor each of the input numbers into prime factors; for now, we will assume that these numbers are easy to factor. For the above example set, we get:

10 = 2 × 524 = 2When you multiply two numbers written as prime factorizations, you simply add the exponents of the primes used. For example, the exponent of 2 in 24×52×78 is 6, because it’s 3 in 24, 2 in 52, and 1 in 78. A number is a square if and only if all the exponents in its prime factorization are even. Suppose we write the above factorizations as vectors, where the *k*^{th} entry corresponds to the exponent of the *k*^{th} prime number. We get:

Now, multiplying numbers is as simple as adding vectors. If we add rows 2, 4, and 6, we get [6 2 0 0 0 2], which has all even exponents and so must be a square. In more familiar terms, we want the last bit of each entry in the sum to be zero. But in this case, we don’t need to store all of the numbers above, only the last bit of each number. This gives us the following:

[1 0 1 0 0 0][1 1 0 0 0 0][0 0 1 1 0 0][0 0 0 0 0Moreover, since we’re only interested in last bits, we can perform all our addition using one-bit integers with wraparound semantics (in other words, mod 2). If we add rows 2, 4, and 6 in this way, we get [0 0 0 0 0 0 0], the zero vector. In fact, all squares correspond to the zero vector.

Let’s rephrase this as a matrix equation problem. If we transpose the above matrix, so that rows become columns, we get this:

[1 1 0 0 1Call this matrix A. If we multiply A by the vector [0 1 0 1 0 1], using one-bit integer arithmetic, we get the zero vector. This tells us precisely which numbers we need to multiply to get a square. So, our goal is to find a nonzero vector x such that Ax=0 (remember, all arithmetic here is with one-bit integers).

Search this Book:

Reset