exp(pi * sqrt(n))が整数に近くなるnを探す
Posted feedbacks - Java
強引に解いてみました。BigDecimalを使用していますがライブラリがないので自前で計算しています。expの計算方法が非効率的なので非常に時間がかかります（苦笑）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | import java.math.BigDecimal;
import java.math.MathContext;
public class Sample {
private static final double EPS = 0.000001;
private static final double EPS2 = 1e-25;
private static final BigDecimal TWO = new BigDecimal(2);
private static final BigDecimal PI = new BigDecimal
("3.1415926535897932384626433");
public static BigDecimal exp(BigDecimal x) {
int i = 1;
BigDecimal b = new BigDecimal(i++);
BigDecimal c = x;
BigDecimal a = new BigDecimal(1.0);
BigDecimal d;
while ((d = c.divide(b, MathContext.DECIMAL128)).doubleValue() > EPS) {
a = a.add(d);
b = b.multiply(new BigDecimal(i++));
c = c.multiply(x);
}
return a;
}
public static BigDecimal sqrt(BigDecimal a) {
BigDecimal x = new BigDecimal(10);
BigDecimal delta;
do {
delta = (x.multiply(x).subtract(a)).divide(TWO.multiply(x),
MathContext.DECIMAL128);
x = x.subtract(delta);
} while (delta.abs().doubleValue() > EPS2);
return x;
}
public static void main(String[] args) {
for (int i = 1; i < 200; i++) {
BigDecimal er = exp(PI.multiply(sqrt(new BigDecimal(i))));
BigDecimal rer = new BigDecimal(er.toBigInteger());
double a = er.subtract(rer).doubleValue();
if (a < 0.0001 || a > 0.9999) {
System.out.printf("%d: %f%n", i, er);
}
}
}
}
|
expの計算の効率を上げる事で、なんとか実用(?)的な性能にする事ができました。
x = n log 10 + k の時
exp(x) = 10^n * exp(k)
の性質を使っています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | import java.math.BigDecimal;
import java.math.MathContext;
public class Sample {
private static final double EPS = 0.000001;
private static final double EPS2 = 1e-25;
private static final BigDecimal TWO = new BigDecimal(2);
private static final BigDecimal PI = new BigDecimal
("3.141592653589793238462643383279");
private static final BigDecimal LN10 = new BigDecimal
("2.3025850929940456840179914546844");
public static BigDecimal exp(BigDecimal x) {
BigDecimal[] dr = x.divideAndRemainder(LN10);
int n = dr[0].intValue();
x = dr[1];
int i = 1;
BigDecimal b = new BigDecimal(i++);
BigDecimal c = x.scaleByPowerOfTen(n);;
BigDecimal a = new BigDecimal(1.0).scaleByPowerOfTen(n);
BigDecimal d;
while ((d = c.divide(b, MathContext.DECIMAL128)).doubleValue() > EPS) {
a = a.add(d);
b = b.multiply(new BigDecimal(i++));
c = c.multiply(x);
}
return a;
}
public static BigDecimal sqrt(BigDecimal a) {
BigDecimal x = new BigDecimal(Math.sqrt(a.doubleValue()));
BigDecimal delta;
do {
delta = (x.multiply(x).subtract(a)).divide(TWO.multiply(x),
MathContext.DECIMAL128);
x = x.subtract(delta);
} while (delta.abs().doubleValue() > EPS2);
return x;
}
public static void main(String[] args) {
for (int i = 1; i < 200; i++) {
BigDecimal er = exp(PI.multiply(sqrt(new BigDecimal(i))));
BigDecimal rer = new BigDecimal(er.toBigInteger());
double a = er.subtract(rer).doubleValue();
if (a < 0.0001 || a > 0.9999) {
System.out.printf("%d: %f%n", i, er);
}
}
}
}
|
herumi
#3416()
Rating0/2=0.00
Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。
この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。[ reply ]