What pairs of digits will cause a carry? Consider the following table:
0 1 2 3 4 5 6 7 8 9
0 . . . . . . . . . +
1 . . . . . . . . + x
2 . . . . . . . + x x
3 . . . . . . + x x x
4 . . . . . + x x x x
5 . . . . + x x x x x
6 . . . + x x x x x x
7 . . + x x x x x x x
8 . + x x x x x x x x
9 + x x x x x x x x x
An x indicates that the given pair of digits will always cause a carry. A + indicates that the pair will cause a carry if and only if there was a carry coming into the addition of the digit pair. A dot indicates no carry coming out of the addition of this pair.
The first (rightmost) digit pair can never have a carry coming into it. The leftmost digit pair cannot contain a zero. The remaining digit(s) can have either. For larger than 3-digit numbers the middle digits can have varying probabilities of having a carry coming into them depending on how far from the right they are.
Starting at the right ends of the pair of 3-digit numbers:
The probability of a carry is 45/100 = 9/20 (or technically, 45/81 if in the general case we're talking about 1-digit numbers, so as to exclude zeros).
Going to the 10's digit, there's a 9/20 probability it will have a carry coming into it, so we must give a 9/20 weight to the probability of a carry going out of it given that a carry came in, and an 11/20 (i.e. 55/100) weight to the probability given that a carry did not come in. But actually we're interested in counting the carries, so it's pretty useless to consider the overall probability of sending a carry to the 100's digit pair. So:
prob of no carry, no carry: (11/20)^2
prob of no carry, carry: (11/20)*(9/20)
prob of carry, no carry: (9/20)*(9/20)
prob of carry, carry: (9/20)*(11/20)
So, going into the 100's digit there's:
(i) prob of carry count = 0, no carry going in now: (11/20)^2 = 121/400
(ii) prob of carry count = 1, no carry going in now: (9/20)^2 = 81/400
(iii) prob of carry count = 1, carry going in now: 99/400
(iv) prob of carry count = 2, carry going in now: 99/400
For the calculation of that last digit (100's digit), we must consider that if there is no carry going into it there is a 45/81 probability there will be a carry coming out; if there is a carry going in there's a 53/81 probability of a carry going out (making the sum a 4-digit number from two 3-digit numbers).
(i) 0 -> 0 (11/20)^2 * 36/81 = 121/900
(i) 0 -> 1 (11/20)^2 * 45/81 = 121/720
(ii) 1 -> 1 (9/20)^2 * 36/81 = 9/100
(ii) 1 -> 2 (9/20)^2 * 45/81 = 9/80
(iii) 1 -> 1 99/400 * 28/81 = 77/900
(iii) 1 -> 2 99/400 * 53/81 = 583/3600
(iv) 2 -> 2 99/400 * 28/81 = 77/900
(iv) 2 -> 3 99/400 * 53/81 = 583/3600
p(0) = 121/900 = 121/900 ~= .134444444444444
p(1) = 121/720 + 9/100 + 77/900 = 1237/3600 ~= .343611111111112
p(2) = 9/80 + 583/3600 + 77/900 = 9/25 ~= .36
p(3) = 583/3600 = 583/3600 ~= .161944444444444
A program for more generalized case:
10 dim ProbCtOv(10,1),NewProbCtOv(10,1)
20 kill "2grdmath.txt": open "2grdmath.txt" for output as #2
30 for N=1 to 6
40 erase ProbCtOv():dim ProbCtOv(10,1)
50 ProbCtOv(0,0)=1
60 ProbCtOv(0,1)=0
70 for K=1 to N
80 erase NewProbCtOv():dim NewProbCtOv(10,1)
90 if K<N then POvOv=11//20:PNOvOv=9//20
100 :else POvOv=53//81:PNOvOv=45//81
110 POvNOv=1-POvOv:PNOvNOv=1-PNOvOv
115 for I=0 to N
120 NewProbCtOv(I,0)=NewProbCtOv(I,0)+ProbCtOv(I,0)*PNOvNOv
130 NewProbCtOv(I+1,1)=NewProbCtOv(I+1,1)+ProbCtOv(I,0)*PNOvOv
140 NewProbCtOv(I,0)=NewProbCtOv(I,0)+ProbCtOv(I,1)*POvNOv
150 NewProbCtOv(I+1,1)=NewProbCtOv(I+1,1)+ProbCtOv(I,1)*POvOv
155 next I
160 for I=0 to N
170 ProbCtOv(I,0)=NewProbCtOv(I,0)
180 ProbCtOv(I,1)=NewProbCtOv(I,1)
190 next
200 next K
210 print N
220 for I=0 to N
230 print ProbCtOv(I,0)+ProbCtOv(I,1),
235 print #2, ProbCtOv(I,0)+ProbCtOv(I,1),
240 next I
250 print:print #2,
260 next N
270 close #2
produces the following info for numbers of carries from zero to n (annotated by hand with double /'s replaced by single):
digits number of carries probabilities
n 0 1 2 3 ...
1 4/9 5/9
2 11/45 83/180 53/180
3 121/900 1237/3600 9/25 583/3600
4 1331/18000 17171/72000 2727/8000 2061/8000 6413/72000
5 14641/360000 45617/288000 22743/80000 11727/40000 13959/80000 70543/1440000
6 161051/7200000 2940179/28800000 702801/3200000 453627/1600000 370323/1600000 72963/640000 775973/28800000
With decimals shown:
0 1 2 3 4 5 6 7 8 9
1
0.4444444 0.5555556
2
0.2444444 0.4611111 0.2944444
3
0.1344444 0.3436111 0.3600000 0.1619444
4
0.0739444 0.2384861 0.3408750 0.2576250 0.0890694
5
0.0406694 0.1583924 0.2842875 0.2931750 0.1744875 0.0489882
6
0.0223682 0.1020895 0.2196253 0.2835169 0.2314519 0.1140047 0.0269435
7
0.0123025 0.0643848 0.1611039 0.2482995 0.2539153 0.1725524 0.0726227 0.0148189
8
0.0067664 0.0399412 0.1138099 0.2032093 0.2478664 0.2114120 0.1234458 0.0453985 0.0081504
9
0.0037215 0.0244589 0.0781246 0.1582502 0.2232617 0.2272116 0.1669166 0.0856021 0.0279700 0.0044827
Edited on January 12, 2017, 2:49 pm
|
|
Posted by Charlie
on 2017-01-12 14:48:35 |
solution
