Wikipedia:Reference desk/Archives/Mathematics/2011 June 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 30

Factorising an integer into 2 integers

What is a good way to factorise a 16-bit integer into 2 8-bit integers so that the product is as close to the 16-bit integer as possible? I'm trying to emulate a high resolution PWM signal with 2 8-bit PWMs, one running at 1/256 of the clock speed of the other, so that PWM-A would have completed a whole period in the time PWM-B completes 1 count. Therefore the overall duty cycle = A*B/65536, except with reduced precision as the duty cycle increases (which is not a problem). I need to set A*B to any arbitrary amount but I'm not sure how to factorise it, since most factorisation articles focus on prime factorisation with 2+ factors. I thought of an algorithm that shifts the 16-bit integer to the right until it fits in an 8-bit integer and store that into A, while shifting B leftwards by the same amount, effectively reducing the problem to X ~= A * 2^N. This is done on a small microcontroller so things like floating point numbers need to be avoided. Is there a better but still reasonably simple algorithm that can achieve better precision? Thanks. --antilived^{T | C | G} 03:05, 30 June 2011 (UTC)

Is there some reason why you can't just use the first 8 bits as one number and the last 8 bits as the other ? StuRat (talk) 03:11, 30 June 2011 (UTC)

No, because of numbers like 0x0100 would actually give me 0 duty cycle. Basically I'm masking PWM-A with PWM-B - so for example if PWM-B is set to 1 then at the output there would only be a pulse generated by PWM-A 1/256 of the time - or PWM-A AND PWM-B. To achieve what's equivalent to 0x0100 on a 16-bit PWM timer I need to put in either 0x01FF or 0x027F or one of the other combinations, except finding the best combination has been quite challenging. --antilived^{T | C | G} 08:49, 30 June 2011 (UTC)

Gosh that takes me back. I once produced a watchdog timer using two spare serial comms timers linked up like that. I'm afraid I can't think of any better way rather than starting with zero and 255 as the two values and incrementing one number till the product is too high then decreasing the other till it is too low and repeating till one goes out of range, all the while comparing the product with the target and recoding when you get a result that is closer. Actually you can just start with the negative of the number and add or subtract one of the numbers as the other is incremented or decremented, that way you never do an actual multiplication and the difference is there all the time so you can find the closest negative and positive ones. You're talking about at most 256 increments or decrements so it might be okay for you. The general problem is equivalent to factorizing a large number and that is a difficult problem used to making secure cyphers. Dmcq (talk) 07:18, 30 June 2011 (UTC)

Atmel AVRs actually have a hardware multiplication instruction for 8-bit numbers so multiplications don't have that much of a penalty. I'll try out your way and see how well that works - although now to think of it perhaps it's not as big a problem as I thought it would be. I'm doing brightness control on LEDs and accuracy is only important at low intensities. Since the error is proportional to 2^N but the brightness function is also ~2^N the perceived error would be constant and not really a problem at all. I need to experiment with the circuit more; thanks for your help though. --antilived^{T | C | G} 08:49, 30 June 2011 (UTC)

Do you mean you are using a 16-bit integer to specify the brightness of each LED ? That seems excessive. An 8-bit integer should do, giving you 256 brightness possibilities. Since it's easier to perceive the difference between an LED at 0/255 and 1/255 brightness than between 254/255 and 255/255, you may want to use a (nonlinear) look-up table to convert each integer into the true brightness (which might be the 16-bit integer value). Or, you could apply a formula, like 16BIT = 8BIT + round((1.04425788)^(8BIT + 1)) - 1. This formula would give a mapping like so:

  8BIT       16BIT
-------   ----------- 
  0/255       0/65535
  1/255       1/65535
  2/255       2/65535
  3/255       3/65535
  4/255       4/65535
  5/255       5/65535
  6/255       6/65535
  7/255       7/65535
  8/255       8/65535
  9/255      10/65535
        .
        .
        .
253/255   60117/65535
254/255   62767/65535
255/255   65535/65535

StuRat (talk) 14:34, 30 June 2011 (UTC)

Yeah I think given the fact that I will probably have to do some gamma correction too I'd be better off using a LUT, although 256 levels at 2 bytes each takes up half a kilobyte of program space already. Hopefully I won't run out of space! --antilived^{T | C | G} 08:14, 2 July 2011 (UTC)

If the look-up table's too big, then go with the formula I listed, or a similar one. StuRat (talk) 08:26, 3 July 2011 (UTC)

If I understand this correctly, you have a 16 bit integer from 0000000000000000 to 1111111111111111 and you want two 8 bit integers that, when multiplied together, are very close to the original number. So, take the floor of the square root of the 16 bit integer. The result will be an integer from 00000000 to 11111111 (because 11111111² is 1111111111111111). If you like, you can add 1 to one of the two square root factors if the actual result has a fraction that is rather high. Then, you won't lose as much accuracy as using the floor. -- kainaw™ 13:09, 30 June 2011 (UTC)

(edit conflict)Here's an idea: Let N be the number to factor. Let a be the smallest integer greater than √N (use binary search to find this to avoid floating point operations). Let b be the closest integer to N-a². Then N is approximately equal to (a+b)(a-b). E.g. given N=14850, a=122, b=6, 128×116=14848, off by 2.--RDBury (talk) 13:18, 30 June 2011 (UTC)

But 14850 = 99 x 150, so 128 x 116 = 14848 is close, but not "as close as possible". Gandalf61 (talk) 14:12, 30 June 2011 (UTC)

It's still a pretty good algorithm for the job. I like it, just wish I had someplace to use it :) Dmcq (talk) 14:52, 30 June 2011 (UTC)

I think there are some typos in the above. Let me try without typos. Let

${\begin{aligned}a&=\left\lceil {\sqrt {N}}\right\rceil \\b&=\left\lfloor {\sqrt {a^{2}-N}}+1/2\right\rfloor \,.\end{aligned}}$

Then $(a+b)(a-b)$ will be pretty good. —Quantling (talk | contribs) 17:48, 30 June 2011 (UTC)

Alright that's a lot closer than my original idea. I'd have to roll my own integer square root but that doesn't seem too hard. Thanks for the help, I'll use this method if I don't have enough space to store a LUT in the program. --antilived^{T | C | G} 08:14, 2 July 2011 (UTC)

I don't think you need a square root at all. Dmcq gave you a good idea. Use a loop from A=255 going down, in each step computing B which is such that Y=A*B is very close to X, while B<=A, and record the A and B for the Y that's closest to X. You don't need to do any multiplications or divisions for this: if you already have Y=A*B, you compute Y'=(A-1)*B=Y-B, then you compute [Y''=(A-1)*(B-1)=Y'-(A-1)] Y''=(A-1)*(B+1)=Y'+(A-1), then, if Y'' is better then Y' then you [decrease] increase B. – b_jonas 20:11, 4 July 2011 (UTC) [edit: corrected a sign and formatting – b_jonas 20:32, 4 July 2011 (UTC)]

Here's some pseudocode implementing the above idea. I'm not completely sure it's correct, so use it at your own risk.

       input x;
       a = 256;
       b = x >> 8;
       y = b << 8;
       md = 2000;
       mb = 0;
       ma = 0;
       yv = y + a;
       if (yv - x < x - y) {
               b = b + 1;
               y = yv;
       }
       if (64897 < x) {
               ma = mb = 255
       } else {
               do {
                       a = a - 1;
                       y = y - b;
                       yv = y + a;
                       if (yv - x < x - y) {
                               b = b + 1;
                               y = yv;
                       }
                       d = abs(y - x);
                       if (d < md && b < 256) {
                               md = d;
                               ma = a;
                               mb = b;
                       }
               } while (b <= a);
       }
       output ma, mb;

– b_jonas 21:10, 4 July 2011 (UTC)

Gerrymandering Mathematics

I was wondering about this example given in the article on gerrymandering. The article states:

In (a), creating 3 mixed-type districts yields a 3–0 win to Plum — a disproportional result considering the state-wide 9:6 Plum majority.

In (b), Orange wins the urban district while Plum wins the rural districts — the 2-1 result reflects the state-wide vote ratio.

In (c), gerrymandering techniques ensure a 2-1 win to the state-wide minority Orange party.

I would like to know: is this the simplest (fewest voters) and most disproportionate example mathematically possible? Thank you in advance for any help. --CGPGrey (talk) 15:45, 30 June 2011 (UTC)

My reply, reposted from the Humanities desk:

Heck, I'm no mathematician, but it's an easy one if you come from the country that once had Rotten boroughs, like I do. It's definitely not the most extreme example. The most extreme example would be to create 7 districts, one of which contains all the plums and the other six holding one orange each, resulting in a 6-1 victory for orange. Even better would be if you could disbar the plum voters from enfranchisement, gaining a 6-0 whitewash for the party that should have lost. --Dweller (talk) 15:59, 30 June 2011 (UTC)

I think there might be an implied stipulation that the districts be equal in population. In that case I think this is indeed the most distorted possibility. If there are three districts, you have to give one of them to plum, so 2-1 is the best you can do. If there are five districts with three voters each, the best you can do is to make three districts with two orange voters and one plum, leaving two all-plum districts. Overall that comes out 3-2, or again an advantage of 1 for orange, but proportionally less (so plum can win a vote if one orange councilman out of three defects, instead of one out of two). --Trovatore (talk) 21:21, 30 June 2011 (UTC)

How about 3 districts with 3 voting blocks in each:

OOP
PPP
POO

You can get 2/3 P districts by dividing them into 3 columns, or 2/3 O districts by dividing them into 3 rows. StuRat (talk) 16:05, 30 June 2011 (UTC)

Assuming all districts have equal numbers of voters and that every voter belongs to one of two parties, the most extreme possible result is for a party with N% of voters to control 2N% of districts. Thus a party with 10% of voters can control 20% of districts; a party with 50% of voters can control all districts. If there are no constraints on district sizes or on the number of parties, there are no constraints on how extreme the outcome can be. Looie496 (talk) 16:14, 30 June 2011 (UTC)

Thank you. --CGPGrey (talk) 08:00, 3 July 2011 (UTC)

Addendum

When I designed that image to illustrate the article, I realised that in an election with 2 parties, 3 was the smallest number of districts to produce a winning minority, if ties cannot favour either party (so must not happen). Obviously, 1 district can lead only to the stronger party winning. With 2 districts, the best the weaker party can do is to force a 1-1 draw.

I then calculated the fewest voters that 3 districts could be equally divided to yield 3-0 (a), 2-1 (b) and 1-2 (c) results. Let's call give the stronger party S and the weaker one W. S has s voters and W has w voters, making a total of n = s + w voters. The critical cases to satisfy are extreme cases (a) and (c).

Case (a): In each district, S must beat W by the slimmest possible margin i.e. 1 vote (assuming no tie-breaks). Thus for 3 districts, S beats W by 3 votes in total, so s = w + 3.

Case (c): In one district, S must beat W by the greatest possible margin i.e. 100% votes, using up (n/3) S votes. In the 2 remaining districts, W must beat S by the slimmest possible margin i.e. 1 vote (i.e. 2 votes in total), hence w = (s - n/3) + 2. ("- n/3" is due to the votes used up earlier.) Substituting n = s + w gives w = s - (s + w)/3 + 2 or 4w/3 = 2s/3 + 2. Multiplying both sides by 3/2 gives 2w = s + 3.

Solving the 2 simultaneous equations gives s = 9 and w = 6, as in the example. Hope that helps! cmɢʟee☺τaʟκ 00:21, 17 July 2011 (UTC)

P.S. I may not check this page again, so please leave any replies on my talk page. Thanks!

Number of orientations of face centers for Rubik's Cube

Resolved

I believe the Wikipedia article on the Rubik's Cube to be wrong about how many ways there are to orient the six face centers of a Rubik's Cube (when they have markings on them that indicate their orientation); can you help prove me right or wrong? With disassembly of the cube permitted, each of the six centers can be oriented in one of four ways, so there are $4^{6}$ possible orientations; no argument there. But how many orientations can be achieved when disassembly is prohibited? The article says that half of the $4^{6}$ orientations can be achieved, but I believe it to be one quarter of them. In particular, I believe that if the cube has all side and corner pieces arranged and oriented correctly and has five of its six centers oriented correctly then it will necessarily have the sixth center oriented correctly. However, the article indicates, in effect, that it is possible that the sixth center will be 180° out of proper orientation. If the article and its source are indeed correct, what is the "algorithm" that rotates a center by 180° without changing the arrangement or orientation of any other piece? (This paragraph substantially duplicates a discussion I have also tried to start on the Rubik's Cube talk page. If you reply in one of these locations, please consider dropping a quick link at the other.) Thanks! —Quantling (talk | contribs) 17:33, 30 June 2011 (UTC)

Never mind. I figured out the algorithm. —Quantling (talk | contribs) 17:59, 30 June 2011 (UTC)