Factor an integer to something as close to a square as possible

Question

I have a function that reads a file byte by byte and converts it to a floating point array. It also returns the number of elements in said array. Now I want to reshape the array into a 2D array with the shape being as close to a square as possible.

As an example let's look at the number 800:

sqrt(800) = 28.427...

Now by I can figure out by trial and error that 25*32 would be the solution I am looking for. I do this by decrementing the sqrt (rounded to nearest integer) if the result of multiplying the integers is to high, or incrementing them if the result is too low.

I know about algorithms that do this for primes, but this is not a requirement for me. My problem is that even the brute force method I implemented will sometimes get stuck and never finish (which is the reason for my arbitrary limit of iterations):

import math

def factor_int(n):
    nsqrt = math.ceil(math.sqrt(n))

    factors = [nsqrt, nsqrt]
    cd = 0
    result = factors[0] * factors[1]
    ii = 0
    while (result != n or ii > 10000):
        if(result > n):
            factors[cd] -= 1
        else:
            factors[cd] += 1
        result = factors[0] * factors[1]
        print factors, result
        cd = 1 - cd
        ii += 1

    return "resulting factors: {0}".format(factors)

input = 80000
factors = factor_int(input)

using this script above the output will get stuck in a loop printing

[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0

But I wonder if there are more efficient solutions for this? Certainly I can't be the first to want to do something like this.

Demagogic

What if n is a prime. Must it go all the way to n*1 as your factors? – Tristichous

in this case, yes if it does not find two primes before that by chance. I assume that the data I read can always be represented by a rectangle, though. Also now that I think about it, it will probably get stuck then, too.. I change the factor that is incremented or decremented on every other iteration... – Demagogic

I just discussed this question at my blog, and readers gave some ridiculously good solutions, much better than mine, in the comments. Go have a look. – Malley

Answer 1

def factor_int(n):
    val = math.ceil(math.sqrt(n))
    val2 = int(n/val)
    while val2 * val != float(n):
        val -= 1
        val2 = int(n/val)
    return val, val2, n

try it with:

for x in xrange(10, 20):
      print factor_int(x)

           

Tristichous

wow that was fast. I feel dumb now, that I did not think about the n/val ... :D – Demagogic

Cool, there are probably much better ways as well. – Tristichous

well I was not looking for a perfect solution, just for a quick one ! :) – Demagogic

Thanks. This is a "most excellent" solution. – Japhetic

Answer 2

Interesting question, here's a possible solution to your problem:

import math


def min_dist(a, b):
    dist = []
    for Pa in a:
        for Pb in b:
            d = math.sqrt(
                math.pow(Pa[0] - Pb[0], 2) + math.pow(Pa[1] - Pb[1], 2))
            dist.append([d, Pa])

    return sorted(dist, key=lambda x: x[0])


def get_factors(N):
    if N < 1:
        return N

    N2 = N / 2
    NN = math.sqrt(N)

    result = []
    for a in range(1, N2 + 1):
        for b in range(1, N2 + 1):
            if N == (a * b):
                result.append([a, b])

    result = min_dist(result, [[NN, NN]])
    if result:
        return result[0][1]
    else:
        return [N, 1]


for i in range(801):
    print i, get_factors(i)

The key of this method is finding the minimum distance to the cartesian point of [math.sqrt(N), math.sqrt(N)] which meets the requirements N=a*b, a&b integers.

Rentsch

I like your answer, because your approach has the mathematics behind the problem :) I compared the results to the results of the answer I accepted and they both give the same results (at least for integers between 1 and 100000) – Demagogic

@Demagogic I'm sure my solution can be optimized further (right now is brute-force) but at least gives the insights to solve your problem – Rentsch

Answer 3

I think the modulus operator is a good fit for this problem:

import math 

def factint(n):
    pos_n = abs(n)
    max_candidate = int(math.sqrt(pos_n))
    for candidate in xrange(max_candidate, 0, -1):
        if pos_n % candidate == 0:
            break
    return candidate, n / candidate

Eolande

Answer 4

Here's a direct method that finds the smallest, closest integers a, b, such that a * b >= n, and a <= b, where n is any number:

def factor_int(n):
    a = math.floor(math.sqrt(n))
    b = math.ceil(n/float(a))
    return a, b

try it with:

for x in xrange(10, 20):
    print factor_int(x)

Tamarin

The question is asking for a * b == n, not a * b >= n. – Unwell

This is create for a tile scheme (rows/colums) in UI with variable amount of items. – Lindsy

Answer 5

Here's a shorter code based on the currently accepted answer that is shorter and takes about 25%-75% less time to run than their code (from basic timeit tests):

from math import sqrt, ceil
def factor_int_2(n):
    val = ceil(sqrt(n))
    while True:
        if not n%val:
            val2 = n//val
            break
        val -= 1
return val, val2

And here's a small and messy test I made to test the efficiency of the method:

print("Method 2 is shorter and about {}% quicker".format(100*(1 - timeit(lambda: factor_int_2(12345))/timeit(lambda: factor_int(12345)))))
#returns 'Method 2 is shorter and about 75.03810670186826% quicker'

Glaser

Answer 6

Oneline code for one number:

import numpy as np
n = 800
(np.ceil(np.sqrt(n)), np.ceil(n/np.ceil(np.sqrt(n))))

---

>>> (29.0, 28.0)

Not sure if it is what you asked for, but this is much closer to square than (25,32) as you mentioned in the description. Hope it helps!

Heterozygous

it's closer to a square, but 29*28 is not 800... – Demagogic

Answer 7

This is equivalent to finding factors (b,c) for a=b*c such that the smaller factor, b, is the largest number not larger than sqrt(a). This can be solved by:

import math

def closest_factors(a):
    for b in range(int(math.sqrt(a)), 0, -1):
        if a%b == 0:
            c = a // b
            return (b,c)

 print(closest_factors(800))

returns (25,32).

Ledesma