For the math nerds...

[ofnuts]

Not really programming, but...

Gimp has a "raw image data" format that just saves the RGB triplets, but doesn't save anything else (in particular, the image dimensions). So if you forgot the dimensions you are in rough waters. However, since it saves exactly three bytes per pixel, you can tell how many pixels there are in the picture (so you have the width*height product), and you will in practice have bounds for the aspect ratio (for most pictures, between 1 and 2 for landscape and 0.5 and 1 for portrait).

Hence the question: is there a smart algorithm to obtain all the (W,H) pairs that satisfy both conditions? My smarter algorithm so far is a brute force test of all the combination of the prime factors of the product...

[ehrt74]

http://en.wikipedia.org/wiki/Integer_factorization

I wonder which format for Gimp you mean. PPM for example contains a header with the height and width of the file.

[ofnuts]

http://en.wikipedia.org/wiki/Integer_factorization

I wonder which format for Gimp you mean. PPM for example contains a header with the height and width of the file.

The factorization isn't that hard. Given the numbers plain algorithms are sufficient. The "problem" is after the factorization.

As to the format produced by Gimp, I'm talking about that one:

[trent.josephsen]

Hmm, interesting...

If you want to generate *all* the possible WxH combinations, I wouldn't think you could improve on brute force (with some logic to skip combinations you've already tried). Which is a pain because it requires a lot of Cartesian products...

Perhaps you could start not by factoring the number completely, but by splitting it as close to the square root as possible. That way you could start with the aspect ratios that are close to 1 and work your way down. Something like

aspect_ratios(product)
    let k = floor(sqrt(product))
    if k*k = product then
        let (k, k) be a result
    while k > 1
        let k = k - 1
        if product is divisible by k then
            let (k, product/k) be a result
            let (product/k, k) be another

This method has time complexity O(sqrt(n)) but I don't know how to calculate that of the Cartesian product method. My algorithm would likely consume less memory, though, unless you could do something really clever with the brute force method.

The biggest area for optimization might be the "let k = k - 1" part. If you can figure out how to skip over some numbers without testing them... I don't really know, I just thought it was an interesting problem.

[ofnuts]

Well assuming I have split the factors in two groups that are as close as possible to the square root, it's is clear that if I move a factor from one group to the other I change the ratio by the square of this factor (so, 4 minimum) so for ordinary pictures this won't happen. I can only swap factors between the groups if these factors have between them a ratio smaller than sqrt(max_aspect_ratio)(moving a factor as above can be seen as swapping it with a "1"), so to check each factor on one side against every factor on the other I would try only n/2 x n/2 swaps (assuming a 50/50 split of the factors).

But this, of course, assumes there is a good algorithm to "split the factors in two groups that are as close as possible to the square root".

[Warren Hill]

Not a programming solution as such but a simple math based approach.

You know the number of pixels in the image say

p = 480000

Now factorise it

p = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 3 x 5

now length is some combination of these factors and height is all the other factors

so possibilites are

1 x 480000
2 x 240000
3 x 160000
4 x 120000
5 x 96000
6 x 80000
8 x 60000
10 x 48000
15 x 32000
16 x 30000
20 x 24000
30 x 16000
32 x 15000

etc this gives 90 possible solutions

A second simpler but slightly less efficient solution is to start by taking the square root of the total number of pixels. One side must be no bigger than this.

Now for every number 1<= x < sqrt(p)
Calculate other side if its an integer then its possibly a solution
remembering that just as 600 x 800 = 480000 so does 800 x 600 so you would have to try it both ways round.

Its a simple exercise to code this in C or any other language

[trent.josephsen]

(Edit: This was supposed to be in response to ofnuts' last post.)

Right, and a systematic way of swapping between groups so that you don't lose track of which combinations you've already tried...

No, wait, that still wouldn't work, because you still have to swap composite factors. Like if you have 2*3*5 on one side and 2^2*11 on the other, 11/5 might be greater than sqrt(max_aspect_ratio) but 11/10 might not be. So you have to swap 2*5 with 11.

Even disregarding the resources it would take to split the number into two sets of prime factors, you'd probably still be looking at (at least) O(n) for the rest of the algorithm in both time and memory.

(Disclaimer: I'm not taking these complexity estimations from any real figuring, just wild guesses. Actual benchmarking with realistic numbers would be preferable anyway.)

[Bachstelze]

Any half-decent CAS will let you iterate over all divisors of a given integer, and it's easy to go from there. For example in PARI/GP:

? n = 480000
%5 = 480000
? fordiv(n, w, h = n\w; r = w/h; if(r >= 1 && r <= 2, print([w, h])))
[750, 640]
[768, 625]
[800, 600]
[960, 500]
?

If you find the syntax awful, look into Sage (it is based on Python and uses the same syntax). Also, PARI comes with a C library if you want to integrate it in a C program.

[Vaphell]

going from sqrt(n) down to 1 and checking if n%x==0 is plenty fast
i whipped up awk code (to avoid the hassle of creating files) that finds 60 pairs for n=240078886800 (number pulled out of the 4 letters) in under 1 second.

$ echo | awk 'BEGIN{ n=240078886800; } { for( x=int(sqrt(n)); x>0; x--) { if(n%x==0) { c++; printf("%dx%d (ar=%f)\n", n/x, x, n/x/x ); } } } END { print c " combinations (x2)"; }'
510285x470480 (ar=1.084605)
544304x441075 (ar=1.234040)
588100x408228 (ar=1.440617)
680380x352860 (ar=1.928187)
705720x340190 (ar=2.074488)
816456x294050 (ar=2.776589)
850475x282288 (ar=3.012792)
882150x272152 (ar=3.241387)
1020570x235240 (ar=4.338420)
1176200x204114 (ar=5.762466)
1360760x176430 (ar=7.712747)
1411440x170095 (ar=8.297951)
1632912x147025 (ar=11.106356)
1700950x141144 (ar=12.051168)
1764300x136076 (ar=12.965549)
2041140x117620 (ar=17.353681)
2352400x102057 (ar=23.049864)
2551425x94096 (ar=27.115127)
2721520x88215 (ar=30.850989)
3401900x70572 (ar=48.204670)
3528600x68038 (ar=51.862195)
4082280x58810 (ar=69.414725)
5102850x47048 (ar=108.460508)
6803800x35286 (ar=192.818682)
7057200x34019 (ar=207.448779)
8164560x29405 (ar=277.658902)
10205700x23524 (ar=433.842034)
13607600x17643 (ar=771.274727)
20411400x11762 (ar=1735.368135)
40822800x5881 (ar=6941.472539)
200065739x1200 (ar=166721.449167)
400131478x600 (ar=666885.796667)
600197217x400 (ar=1500493.042500)
800262956x300 (ar=2667543.186667)
1000328695x240 (ar=4168036.229167)
1200394434x200 (ar=6001972.170000)
1600525912x150 (ar=10670172.746667)
2000657390x120 (ar=16672144.916667)
2400788868x100 (ar=24007888.680000)
3000986085x80 (ar=37512326.062500)
3201051824x75 (ar=42680690.986667)
4001314780x60 (ar=66688579.666667)
4801577736x50 (ar=96031554.720000)
5001643475x48 (ar=104200905.729167)
6001972170x40 (ar=150049304.250000)
8002629560x30 (ar=266754318.666667)
9603155472x25 (ar=384126218.880000)
10003286950x24 (ar=416803622.916667)
12003944340x20 (ar=600197217.000000)
15004930425x16 (ar=937808151.562500)
16005259120x15 (ar=1067017274.666667)
20006573900x12 (ar=1667214491.666667)
24007888680x10 (ar=2400788868.000000)
30009860850x8 (ar=3751232606.250000)
40013147800x6 (ar=6668857966.666667)
48015777360x5 (ar=9603155472.000000)
60019721700x4 (ar=15004930425.000000)
80026295600x3 (ar=26675431866.666668)
120039443400x2 (ar=60019721700.000000)
240078886800x1 (ar=240078886800.000000)
60 combinations (x2)

with AR cutoff

$ echo | awk 'BEGIN{ n=240078886800; ar=2; } { for( x=int(sqrt(n)); x>0; x--) { if(n%x==0) { if(n/x/x > ar) break; c++; printf("%dx%d (ar=%f)\n", n/x, x, n/x/x ); } } } END { print c " combinations (x2)"; }'
510285x470480 (ar=1.084605)
544304x441075 (ar=1.234040)
588100x408228 (ar=1.440617)
680380x352860 (ar=1.928187)
4 combinations (x2)

[spjackson]

p = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 3 x 5

You are missing a few 5s there.

A second simpler but slightly less efficient solution is to start by taking the square root of the total number of pixels. One side must be no bigger than this.

Now for every number 1<= x < sqrt(p)

Taking the required aspect ratio into consideration, it can be shown that sqrt(p)/sqrt(2) <= x <= sqrt(p), where x is the shorter side (or p is square).