user1043761 user1043761 - 22 days ago 7
C++ Question

Most equivalent factors of a number

Given a number 'n', which is a power-of-2, how can I efficiently find the 2 factors which are most equivalent to eachother? In other words, if I have a linear array and want to map it to 2D, how can I find the 2D dimensions that are the most equal (image dimensions most close to a square)?

Gotta be some kind of bitwise operation to make this fast, rather than looping over factors.

Answer

n is representable as 2^k (since you say it's a power of 2). If k is even, then n == 2^(k/2) * 2^(k/2) (e.g. 16==4*4). If k is odd, then the closest you can get is n == 2^((k-1)/2) * 2^((k+1)/2) (e.g. 8==2*4)

Comments