Paste: euler255 (crappy)

Author:	Jon
Mode:	factor
Date:	Thu, 17 Sep 2009 17:04:00

Plain Text |

Delete Paste

! Copyright (C) 2009 Jon Harper.
! See http://factorcode.org/license.txt for BSD license.
USING: project-euler.common math kernel sequences math.functions math.ranges prettyprint io threads math.parser locals arrays ;
IN: project-euler.255

! http://projecteuler.net/index.php?section=problems&id=255

! DESCRIPTION
! -----------
! We define the rounded-square-root of a positive integer n as the square root of n rounded to the nearest integer.
! 
! The following procedure (essentially Heron's method adapted to integer arithmetic) finds the rounded-square-root of n:
! 
! Let d be the number of digits of the number n.
! If d is odd, set x_(0) = 2×10^((d-1)⁄2).
! If d is even, set x_(0) = 7×10^((d-2)⁄2).
! Repeat:
! 
! until x_(k+1) = x_(k).
! 
! As an example, let us find the rounded-square-root of n = 4321.
! n has 4 digits, so x_(0) = 7×10^((4-2)⁄2) = 70.
! 
! Since x_(2) = x_(1), we stop here.
! So, after just two iterations, we have found that the rounded-square-root of 4321 is 66 (the actual square root is 65.7343137…).
! 
! The number of iterations required when using this method is surprisingly low.
! For example, we can find the rounded-square-root of a 5-digit integer (10,000 ≤ n ≤ 99,999) with an average of 3.2102888889 iterations (the average value was rounded to 10 decimal places).
! 
! Using the procedure described above, what is the average number of iterations required to find the rounded-square-root of a 14-digit number (10^(13) ≤ n < 10^(14))?
! Give your answer rounded to 10 decimal places.
! 
! Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and ceiling function respectively.
! 

! the number length function from project-euler.common doesn't work.

: sum-push ( elt vector -- )
    [ pop  + ] keep push ; 

: my-push ( elt vector -- )
    dup empty? [ push ] [ sum-push ] if ; inline

: my-accumulator ( quot -- quot' vec )
    V{ } clone [ [ my-push ] curry compose ] keep ; inline

: produce-sum ( pred: ( -- ? ) quot: ( -- elt ) -- sum )
    my-accumulator [ while ] dip dup empty? [ drop 0 ] [ first ] if ; inline

: my-number-length ( i -- l ) number>string length ;

: x0 ( i -- x0 )
    my-number-length dup even? 
    [ 2 - 2 / 10 swap ^ 7 * ]
    [ 1 - 2 / 10 swap ^ 2 * ] if ;

: xk+1 ( n xk -- xk+1 )
    [ / ceiling ] keep + 2 / floor ;

: next-multiple ( a multiple -- next )
    [ [ 1 - ] dip /i 1 + ] keep * ;

DEFER: iteration#
:: f ( i xi a b -- iterations# )
a xi xk+1 dup xi = 
    [ drop i b a - 1 + * ] 
    [ i 1 + swap a b iteration# ] if ;

:: iteration# ( i xi a b -- # )
    a a xi next-multiple 
        [ dup b < ] 
        [ [ nip [ 1 + ] [ xi + ] bi ] 2keep [ i xi ] 2dip f ] produce-sum 
    [ drop b [ i xi ] 2dip f ] dip
    + ;

: (euler255) ( a b -- answer ) 
[ 10 swap ^ ] [ 10 swap ^ 1 - ] bi*
[ [ drop x0 1 swap ] 2keep iteration# ] 2keep
swap - 1 + / >float ;

: euler255 ( -- answer ) 
13 14 (euler255) ;

Annotation: Faster

Author:	jon
Mode:	factor
Date:	Thu, 17 Sep 2009 18:59:54

Plain Text |

Delete Annotation

! Copyright (C) 2009 Jon Harper.
! See http://factorcode.org/license.txt for BSD license.
USING: project-euler.common math kernel sequences math.functions math.ranges prettyprint io threads math.parser locals arrays namespaces ;
IN: project-euler.255

! http://projecteuler.net/index.php?section=problems&id=255

! DESCRIPTION
! -----------
! We define the rounded-square-root of a positive integer n as the square root of n rounded to the nearest integer.
! 
! The following procedure (essentially Heron's method adapted to integer arithmetic) finds the rounded-square-root of n:
! 
! Let d be the number of digits of the number n.
! If d is odd, set x_(0) = 2×10^((d-1)⁄2).
! If d is even, set x_(0) = 7×10^((d-2)⁄2).
! Repeat:
! 
! until x_(k+1) = x_(k).
! 
! As an example, let us find the rounded-square-root of n = 4321.
! n has 4 digits, so x_(0) = 7×10^((4-2)⁄2) = 70.
! 
! Since x_(2) = x_(1), we stop here.
! So, after just two iterations, we have found that the rounded-square-root of 4321 is 66 (the actual square root is 65.7343137…).
! 
! The number of iterations required when using this method is surprisingly low.
! For example, we can find the rounded-square-root of a 5-digit integer (10,000 ≤ n ≤ 99,999) with an average of 3.2102888889 iterations (the average value was rounded to 10 decimal places).
! 
! Using the procedure described above, what is the average number of iterations required to find the rounded-square-root of a 14-digit number (10^(13) ≤ n < 10^(14))?
! Give your answer rounded to 10 decimal places.
! 
! Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and ceiling function respectively.
! 

! the number length function from project-euler.common doesn't work.

: produce-sum ( pred quot -- sum )
    [ 0 ] 2dip [ [ dip swap ] curry ] [ [ dip + ] curry ] bi* while ; inline

: my-number-length ( i -- l ) number>string length ;

: x0 ( i -- x0 )
    my-number-length dup even? 
    [ 2 - 2 / 10 swap ^ 7 * ]
    [ 1 - 2 / 10 swap ^ 2 * ] if ;

: xk+1 ( n xk -- xk+1 )
    [ [ 1 - + ] keep /i ] keep + 2 /i ;

: next-multiple ( a multiple -- next )
    [ [ 1 - ] dip /i 1 + ] keep * ;

DEFER: iteration#
:: f ( i xi a b -- iterations# )
a xi xk+1 dup xi = 
    [ drop i b a - 1 + * ] 
    [ i 1 + swap a b iteration# ] if ;

:: iteration# ( i xi a b -- # )
    a a xi next-multiple 
        [ dup b < ] 
        [ [ nip [ 1 + ] [ xi + ] bi ] 2keep [ i xi ] 2dip f ] produce-sum 
    [ drop b [ i xi ] 2dip f ] dip
    + ;

: (euler255) ( a b -- answer ) 
[ 10 swap ^ ] [ 10 swap ^ 1 - ] bi*
[ [ drop x0 1 swap ] 2keep iteration# ] 2keep
swap - 1 + / >float ;

: euler255 ( -- answer ) 
13 14 (euler255) ;

Annotation: Java version

Author:	Jon
Mode:	factor
Date:	Thu, 17 Sep 2009 19:04:55

Plain Text |

Delete Annotation

public class Euler255 {

	static double totalcounts = 0;
	public static void main(String[] args) {
		long a = (long) Math.pow(10, 13); 
		long b = (long) Math.pow(10, 14)-1; 
		a = (long) Math.pow(10, 13); 
		b = (long) Math.pow(10, 14)-1; 
		long xzero = xzero((long) a);
		long time = System.currentTimeMillis();
		count(a,b,1,xzero);
		System.out.println(totalcounts/(b-a+1));
		System.out.println("Total Time :" + (System.currentTimeMillis()-time) + "ms");
	}
	
	public static long numberOfIteration(long n) {
		long xk = xzero(n);
		long nextxk = nextxk(n, xk); 
		int count = 1;
		while(xk!=nextxk) {
			xk = nextxk;
			nextxk = nextxk(n,xk);
			count++;
		}
		return count;
	}

	public static long xzero(long n) {
		long d = numberOfDigits(n);
		if (d%2 == 0) {
			return (long) (7*Math.pow(10, (d-2)/2));
		}
		else {
			return (long) (2*Math.pow(10, (d-1)/2));
		}
	}

	public static long numberOfDigits(long n) {
		long count=1;
		while (n/10>0) {
			count++;
			n=n/10;
		}
		return count;
	}

	public static long nextxk(long n, long xk) {
		double n1 = n;
		double toto = n1/xk;
		double tutu = Math.ceil(toto);
		double trtr = tutu + xk;
		double tata = trtr/2;
		double tktk = Math.floor(tata);
		long result = (long) tktk;
		return result;
	}

	public static void count(long a,long b,int iter, long xk) {
		long nexta = nextMultiple(a, xk);
		long nextxk = nextxk(a,xk);

		while (nexta<b) {
			if (xk == nextxk) {
				totalcounts+=iter*(nexta-a+1);
			} else {
				count(a,nexta,iter+1,nextxk);
			}
			a=nexta+1;
			nexta= nexta+xk;
			nextxk=nextxk(a,xk);
		}
		
		if (xk == nextxk) {
			totalcounts+=iter*(b-a+1);
		} else {
			count(a,b,iter+1,nextxk);
		}
	
		
	}

	public static long nextMultiple(long a, long multiple) {
		return (((a-1)/multiple)+1)*multiple;
	}
}

New Annotation

Summary:
Author:
Mode:	textPostgreSQLPowerCenter Parameter Fileactionscriptadaada95ans-forth94antantlrantlr4apacheconfapdlapplescriptaspaspect-jassembly-agcassembly-agsassembly-arm32assembly-m68kassembly-macro32assembly-mcs51assembly-parrotassembly-r2000assembly-x86avroawkbbatchbbjbcelbeanshellbibtexbinsource-agccc#c++cfscriptchillcilclipsclojurecmakecobolcoffeescriptcoldfusioncplex-lpcsscsvcvs-commitddartdjangodockerfiledotdoxygendrawj2ddsssleiffelembperlerlangfactorfhtmlforthfortranfortran90foxprofreemarkergcbasicgettextgherkingnuplotgogradlegroovygsphaskellhaxehexhl7v2hlslhtaccesshtmlhxmli4glicalendariconidlinforminiinno-setupinterlisiojamonjavajava module-infojavaccjavafxjavascriptjcljedit-actionsjflexjhtmljmkjsonjspkotlinlatexlexlilypondlispliterate-haskelllogslogtalklotosluam4macroschedulermailmakefilemaplemarkdownmavenmavscriptmetapostmlmodula3moinmqscmustache-templatemxmlmyghtymysqln3netrexxnqcnsis2objective-cobjectrexxoccamomnimarkopensipsoutlinepascalpatchperlphppikepl-sqlpl-sql9pl1plaintexplantumlpop11postscriptpovraypowerdynamopowershellprogressprologpropertiesprotobufpspptlpurepvwavepyrexpythonqdocrakefilercprdrebolredcoderelax-ng-compactrenderman-ribrestrfcrhtmlroffrpm-specrtfrubyrustrviews#s+sassbtscalaschemesdl/prsgmlshellscriptshtmlsipsippslateslaxsmalltalksmartysmi-mibsparqlsql-loadersqrsquidconfstatasvn-commitswiftswigtcltemplate-toolkittextexinfotldtransact-sqltsptwikityposcripturluscriptvalavbscriptvelocityverilogvhdlvisualbasicvrml2wellknowntextxmlxqxslyabyamlzpt
Body:

Done