Extract the closest two numbers that multiply to create a given number

Question

I made a CPU based raytracer in PyGame which uses a tile per thread to render each section of the screen. Currently I divide the screen vertically between lines, this doesn't give me the best distribution: I want to divide threads in even boxes covering both the X and Y directions. For example: If my resolution is x = 640, y = 320 and I have 4 threads, I want a list of 4 boxes representing tile boundaries in the form (x_min, y_min, x_max, y_max), in this case the result being [(0, 0, 320, 160), (320, 0, 640, 160), (0, 160, 320, 320), (320, 160, 640, 320)].

Problem is I don't see how to automatically divide the number of threads into a 2D grid: I want to extract the closest two whole numbers that multiply to match the thread setting. If this number can't be divided evenly, jump to the closest one that can... for instance no two integers can multiply to create 7, use 6 or 8 instead. I tried math.sqrt but it only works for perfectly divisible numbers like 16, even when rounding that it won't give accurate results for values like 32. What is the simplest solution?

Examples: 4 = 2 * 2, 6 = 2 * 3, 8 = 2 * 4, 9 = 3 * 3, 16 = 4 * 4, 24 = 4 * 6, 32 = 4 * 8, 64 = 8 * 8.

Answer 1

If I understand you correctly, you are looking for the following:

Given a number x > 0, find the pair of factors (z, h) where the absolute difference of (z, h) is the at a minimum.

x is the number of available threads and (z, h) will then be the number of tilings you will have (vertically, horizontally).

If the number of pixels doesn't divide perfectly in your number of tilings, you can add the remainder to the last tiling.

The most efficient algorithm that I can think of is as follows:

• start with x, the number we want to factor.
• calculate sqrt(x) and round it down to the nearest integer. Call this s.
• the smaller factor we're looking for will be the largest divisor of x that's less than or equal to s.

In python code it'll look something like this:

import math

def closest_factors(x):
    s = int(math.sqrt(x))
    
    for z in range(s, 0, -1):
        if x % z == 0:
            return z, x // z

x = 60
factor1, factor2 = closest_factors(x)
print(f"The factors of {x} with the least difference are: {factor1} and {factor2}")
print(f"Their difference is: {abs(factor1 - factor2)}")

There may be a mathematical formula for this that speeds it up, but I'm not familiar with it.

Updated according to @MirceaKitsune 's suggestion in the comments.