Счастливые билеты
index.htm - Russian text
HappyTickets.zip - the archived directory, in which is contained all necessary for this example.
The purpose of the given example is the research of abilities of the supercompiler on acceleration of fulfilment of programs containing another's packages. In given case, package for operation with complex numbers.
The ticket consisting of 6 digits is named happy, if the sum of its first three digits is peer to the sum of last three digits. For example, 123 204 (1+2+3=2+0+4). The definition is extended on arbitrary length of the ticket and arbitrary number system.
There is a task of quantifying of the happy ticket among all 1000000 ticket. The answer is peer 55 252.
The formula for a long time is known
N = (1 / pi) * (integral from 0 up to pi from the function ( sin10x / sin x )6 ).
Generally number 10 is substituted on a base number, number 6 - on length of the ticket. Hereinafter for visualization in all formulas there will be numbers 10 and 6 instead of characters.
Years 10 back I calculated on the computer approximately amount of the happy ticket on reduced above to formula, therefore has detected, that the integral can be exchanged with the final sum. In a magazine Quantum the appropriate article was published.
Here it is offered for calculation of an amount of the happy ticket to use integration in complex area.
The formula is correct
N = (1 / (2*pi*i)) * (integral from the function f (z) on a closed circuit in complex area containing number zero),
Where
f(z) = ( (z10 - 1) / (z - 1) )6 / z28
Thus 10 - the base number, is possible to substitute on any other,
6 - length of the ticket, is possible to change on any other length,
28 = (10 - 1) * (6 / 2) + 1
The second formula actually follows from the process of the proof of the first formula. Let's reduce without details a proof scheme.
1. The amount of the happy ticket is equal to an amount of the ticket with the sum of digits 27.
2. In a polynomial
( 1 + z + z2 + z3 + z4 + z5 + z6 + z7 +z8 + z9 )6
The coefficient at zk is peer to an amount of the ticket with the sum of digits k.
3. Means, the amount of the happy ticket is equal to coefficient at x27 in a polynomial
( (z10 - 1) / (z - 1) )6
The different formulas for an amount of the happy ticket correspond(meet) to different ways of extract of the indicated coefficient them of this polynomial.
4. After division on x28 the amount of the happy ticket will be coefficient at x-1 .
5. Now we use a function theory of a complex variable. The coefficient at x-1 is named as a deduction, which is peer reduced above to integral. In TFKP usually act on the contrary - for calculation of integrals use deductions.
Supercompilation of programs on Java
The package for operation with complex numbers was used
http://www.netlib.org/java/JavaComplex.tgz
http://www.almide.demon.co.uk/html/Complex/Complex_for_Java.html
In the program HappyTickets.java the integration in complex area on a circle of radius 1 with centre in an origin of coordinates is realized.
Variables
public static final int notation = 2;
public static final int lengthTicket = 6;
Set a base number and length of the ticket. All test start-up суперкомплятора were made for a binary number system. More visible programs here are received, and the answer - C2nn .
Through parameters final there is a handle of a specialization. It is possible to receive the residual program, which calculates only amount of the indicated happy ticket (as here). It is possible to receive the common program, which suits any number system and any length of the ticket. It is possible to be restricted to a decimal number system.
The factor of acceleration - 6.5 times.
Let's reduce here text of the program HappyTickets.java and text of the residual program HappyTickets.js. We see, that the supercompilation is ideal in the sense that remained of calls of functions of operation with complex numbers.
/**
* Class for calculation of number of the happy tickets
* through complex numbers.
* For example,
* 123 204 - happy ticket, because the sum 1, 2, 3
* is equal to the sum 2, 0, 4
* 123 254 - is not the happy ticket, because the sum 1, 2, 3
* is not equal to the sum 2, 5, 4
*/
public class HappyTickets{
public static final int notation = 2;
public static final int lengthTicket = 6;
public static final int c28 = (notation-1)*(lengthTicket/2)+1;
public static int numberSteps = 1000000;
public static final Complex Compl1 = new Complex(1.0, 0.0);
public static final Complex Compl0 = new Complex(0.0, 0.0);
public static final Complex i2pi = new Complex(0.0, 2.0 * Math.PI);
public static Complex Compl28 = new Complex(numberSteps, 0.0);
/**
* Calculation of number of the happy tickets
* through complex numbers.
* The formula of calculation
* N = (1.0 / 2*pi*i) *
* integral on the closed contour containing number zero,
* from function
* f(z) = ((z^10 - 1) / (z - 1))^6 / z^28
* where
* 10 - basis of a notation,
* 6 - length of the tickets.
*/
public static void main (String[] args) {
Complex res = new Complex(0.0, 0.0);
for (int it=0; it<5; it++) {
long start = System.currentTimeMillis();
res = test(numberSteps);
res = res.div(i2pi);
System.out.println("result = "+ res);
long end = System.currentTimeMillis();
System.out.println("Total time = "+ (end-start)*0.001);
}
}
/**
* The closed contour is a circle of radius 1
* with the centre in the beginning of coordinates
*/
public static Complex test(int numberSteps1) {
double st = 2.0 * Math.PI / numberSteps1;
Complex eps = new Complex(Math.cos(st), Math.sin(st));
Complex res = new Complex(0.0, 0.0);
Complex epsr = new Complex(1.0, 0.0);
for (int it=0; it<numberSteps1; it++) {
Complex r1 = eps.mul(epsr);
Complex delta = r1.sub(epsr);
res = delta.mul(fi(epsr)).add(res);
epsr = eps.mul(epsr);
}
return res;
}
/** Calculation f(z)
* @param x Complex number z
*/
public static Complex fi(Complex z) {
Complex ff1 = new Complex( 0.0, 0.0);
Complex ff2 = new Complex( 1.0, 0.0);
for (int i=0; i<notation; i++) {
ff1 = ff1.add(ff2);
ff2 = ff2.mul(z);
}
Complex ff3 = degc(ff1, lengthTicket);
Complex ff4 = ff3.mul(degc(z, c28).conj());
return ff4;
}
/** Calculation of a degree of complex number
* @param ccc complex number
* @param ddd degree
*/
public static Complex degc(Complex c, int d) {
Complex r = new Complex( 1.0, 0.0);
for (int i = 0; i < d; i++) {
r = r.mul(c);
}
return r;
}
}
The residual program
//-------------------------------------- 1 sec - postprocessing...
public static ORG.netlib.math.complex.Complex test (final int numberSteps1_29)
{
final double st_33 = 2D * java.lang.Math.PI / (double)numberSteps1_29;
final double re_34 = java.lang.Math.cos(st_33) /*static*/;
final double im_35 = java.lang.Math.sin(st_33) /*static*/;
final ORG.netlib.math.complex.Complex res_39 = new ORG.netlib.math.complex.Complex(0D, 0D);
//- this is res_39 = new ORG.netlib.math.complex.Complex(0D, 0D)
// res_39.re = 0D;
// res_39.im = 0D;
final ORG.netlib.math.complex.Complex epsr_42 = new ORG.netlib.math.complex.Complex(1D, 0D);
//- this is epsr_42 = new ORG.netlib.math.complex.Complex(1D, 0D)
// epsr_42.re = 1D;
// epsr_42.im = 0D;
ORG.netlib.math.complex.Complex res_261 = res_39;
ORG.netlib.math.complex.Complex epsr_260 = epsr_42;
int it_259 = 0;
while (it_259 < numberSteps1_29) {
final double re_282 = re_34 * epsr_260.re - im_35 * epsr_260.im - epsr_260.re;
final double im_284 = re_34 * epsr_260.im + im_35 * epsr_260.re - epsr_260.im;
final double im_304 = epsr_260.im;
final double re_317 = 1D + epsr_260.re;
final double re_363 = re_317 * re_317 - im_304 * im_304;
final double im_366 = re_317 * im_304 + im_304 * re_317;
final double re_379 = re_363 * re_317 - im_366 * im_304;
final double im_382 = re_363 * im_304 + im_366 * re_317;
final double re_395 = re_379 * re_317 - im_382 * im_304;
final double im_398 = re_379 * im_304 + im_382 * re_317;
final double re_411 = re_395 * re_317 - im_398 * im_304;
final double im_414 = re_395 * im_304 + im_398 * re_317;
final double re_427 = re_411 * re_317 - im_414 * im_304;
final double im_430 = re_411 * im_304 + im_414 * re_317;
final double re_453 = epsr_260.re;
final double im_455 = epsr_260.im;
final double re_471 = re_453 * epsr_260.re - im_455 * epsr_260.im;
final double im_476 = re_453 * epsr_260.im + im_455 * epsr_260.re;
final double re_491 = re_471 * epsr_260.re - im_476 * epsr_260.im;
final double im_496 = re_471 * epsr_260.im + im_476 * epsr_260.re;
final double re_511 = re_491 * epsr_260.re - im_496 * epsr_260.im;
final double im_533 = -(re_491 * epsr_260.im + im_496 * epsr_260.re);
final double re_541 = re_427 * re_511 - im_430 * im_533;
final double im_544 = re_427 * im_533 + im_430 * re_511;
final double re_563 = re_282 * re_541 - im_284 * im_544 + res_261.re;
final double im_565 = re_282 * im_544 + im_284 * re_541 + res_261.im;
final ORG.netlib.math.complex.Complex res_566 = new ORG.netlib.math.complex.Complex(re_563, im_565);
//- this is res_566 = new ORG.netlib.math.complex.Complex(re_563, im_565)
// res_566.re = re_563;
// res_566.im = im_565;
final double re_575 = re_34 * epsr_260.re - im_35 * epsr_260.im;
final double im_580 = re_34 * epsr_260.im + im_35 * epsr_260.re;
final ORG.netlib.math.complex.Complex epsr_581 = new ORG.netlib.math.complex.Complex(re_575, im_580);
//- this is epsr_581 = new ORG.netlib.math.complex.Complex(re_575, im_580)
// epsr_581.re = re_575;
// epsr_581.im = im_580;
it_259++;
epsr_260 = epsr_581;
res_261 = res_566;
continue;}
/*while*/
return res_261;
}
//-------------------------------------- 2 sec - JScp version 0.0.75