Google Problem - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

Site Related Forums

The Yak Corral

Google Problem

Author

Topic

jhermiz

3564 Posts

Posted - 2004-07-15 : 10:27:42

Has anyone solved it ?

http://www.google.com/googleblog/

I had a great time this morning doing this rather than
writing my application...I think I should apply

http://www.google.com/labjobs/index.html

If the value of e wasnt so long I'd post my solution

Heh just kidding if anyone attempts and gets stuck ill provide details

Jon
www.web-impulse.com

eyechart
Master Smack Fu Yak Hacker

3575 Posts

Posted - 2004-07-15 : 16:13:42

this would make a good programming challenge here. I would like to see an all SQL solution to this.

-ec

jhermiz

3564 Posts

Posted - 2004-07-15 : 16:29:53

I've got a VB and C++ solution so far :)...dont know enough SQL to post a solution though :(.

I dont want to give the answer :( .. thought we'd have people trying to solve it mathematically :)..thats where it gets fun!!!!

Come on ... I know someone out there wants to take a stab!

Jon
www.web-impulse.com

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-15 : 19:36:40

Im working on a solution (all SQL)

Generate 'e' in SQL
Generate primes in SQL

Then Query. not the fastest way... but who cares - Its Fun

Corey

eyechart
Master Smack Fu Yak Hacker

3575 Posts

Posted - 2004-07-15 : 19:40:48

quote:
Originally posted by Seventhnight

Im working on a solution (all SQL)

Generate 'e' in SQL
Generate primes in SQL

Then Query. not the fastest way... but who cares - Its Fun

Corey

I wrote a function to determine a prime number and I wrote a function that calcuates the factorial (needed to calculate e). However, I am stumped on how to actually calculate e beyond 38 digits.

How are you accomplishing this?

btw, my formula for calculating e is as follows:

e = 1/0! + 1/1! + 1/2! + 1/3! + 1/4! + ...

-ec

eyechart
Master Smack Fu Yak Hacker

3575 Posts

Posted - 2004-07-15 : 19:44:28

I figured I might as well post what I have. I would like to see an all SQL solution to this.

Code for determining a prime number

/* eyechart */
CREATE FUNCTION IS_PRIME (@pn bigint)

RETURNS varchar(10)

as

/* revised to accept a BIGINT instead of INT */

begin

declare @i bigint
declare @stop bigint

set @i = 2
set @stop = ceiling(sqrt(@pn))

while @i <= @stop
 begin
  if @pn % @i = 0 
   begin
    if @i <> @pn return 'not prime' 
   end
  set @i = @i + 1
 end
return 'prime'
end

/*

select dbo.is_prime(1)
select dbo.is_prime(2)
select dbo.is_prime(3)
select dbo.is_prime(4)
select dbo.is_prime(5)
select dbo.is_prime(6)
select dbo.is_prime(10)
select dbo.is_prime(22)

*/

Code to calculate factorial:

/* eyechart */
CREATE FUNCTION dbo.calcfactorial 
(
@base_number decimal(38,0)
)

RETURNS BIGINT

AS

BEGIN

/* SPROC code borrowed from Ken Henderson 
   http://www.awprofessional.com/articles/article.asp?p=25288&seqNum=13 */

DECLARE @factorial bigint

DECLARE @previous_number decimal(38,0)
IF ((@base_number>26) and (@@MAX_PRECISION<38)) OR (@base_number>32) RETURN(-101)  --number too large
IF (@base_number<0) RETURN(-102)  -- Can't calculate negative factorials
IF (@base_number<2) SET @factorial=1 -- Factorial of 0 or 1=1
ELSE BEGIN
 SET @previous_number=@base_number-1
 SELECT @factorial = dbo.calcfactorial (@previous_number) -- Recursive call
 IF (@factorial=-1) RETURN(-103) -- Got an error, return
 SET @factorial=@factorial*@base_number
 IF (@@ERROR<>0) RETURN(-104) -- Got an error, return
END
RETURN @factorial
END

/*

select dbo.calcfactorial(2)
select dbo.calcfactorial(3)
select dbo.calcfactorial(4)
select dbo.calcfactorial(5)
select dbo.calcfactorial(6)
select dbo.calcfactorial(7)

*/

-ec

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-15 : 19:57:21

ec -
first, in your is_prime function you should increment by 2 starting from 3 and discount all even 10-digit numbers...

second, I'm not using factorials. I haven't worked out the exact code for getting past 38 digits, but i know i can do it. let me show you this though:


	Declare @e decimal(38,37),
		@lastStep decimal(38,37)

	Set @e = 1
	Set @lastStep = @e
 
	Select @e = @e + @lastStep/number, @lastStep = @lastStep/number From admin.dbo.getSequence(1,50,1)
	Select @e

I am planning on taking advantage of powers of 10 at certain points, just don't know where yet. Good-luck

Corey

eyechart
Master Smack Fu Yak Hacker

3575 Posts

Posted - 2004-07-15 : 20:12:54

OK, i revised my code with your suggestions.

Also, I have a solution if I provide e (I found e to 10000 places at wikipedia).

btw, I had to change my is_prime function to accept bigint instead of int. Small oversight ;)

EDIT:
when I changed my function to increment by 2 starting from 3 it broke. Seems to work fine as is though.

-ec

eyechart
Master Smack Fu Yak Hacker

3575 Posts

Posted - 2004-07-15 : 21:15:35

OK, here is my solution:

--drop table google_challenge
--create table google_challenge (e text)
--truncate table google_challenge

insert into google_challenge values( 
'2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260
595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069
551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696
770785449969967946864454905987931636889230098793127736178215424999229576351482208269895193668033182528869398496465105820939239829488793320362509443117
301238197068416140397019837679320683282376464804295311802328782509819455815301756717361332069811250996181881593041690351598888519345807273866738589422
879228499892086805825749279610484198444363463244968487560233624827041978623209002160990235304369941849146314093431738143640546253152096183690888707016
768396424378140592714563549061303107208510383750510115747704171898610687396965521267154688957035035402123407849819334321068170121005627880235193033224
745015853904730419957777093503660416997329725088687696640355570716226844716256079882651787134195124665201030592123667719432527867539855894489697096409
754591856956380236370162112047742722836489613422516445078182442352948636372141740238893441247963574370263755294448337998016125492278509257782562092622
648326277933386566481627725164019105900491644998289315056604725802778631864155195653244258698294695930801915298721172556347546396447910145904090586298
496791287406870504895858671747985466775757320568128845920541334053922000113786300945560688166740016984205580403363795376452030402432256613527836951177
883863874439662532249850654995886234281899707733276171783928034946501434558897071942586398772754710962953741521115136835062752602326484728703920764310
059584116612054529703023647254929666938115137322753645098889031360205724817658511806303644281231496550704751025446501172721155519486685080036853228183
152196003735625279449515828418829478761085263981395599006737648292244375287184624578036192981971399147564488262603903381441823262515097482798777996437
308997038886778227138360577297882412561190717663946507063304527954661855096666185664709711344474016070462621568071748187784437143698821855967095910259
686200235371858874856965220005031173439207321139080329363447972735595527734907178379342163701205005451326383544000186323991490705479778056697853358048
966906295119432473099587655236812859041383241160722602998330535370876138939639177957454016137223618789365260538155841587186925538606164779834025435128
439612946035291332594279490433729908573158029095863138268329147711639633709240031689458636060645845925126994655724839186564209752685082307544254599376
917041977780085362730941710163434907696423722294352366125572508814779223151974778060569672538017180776360346245927877846585065605078084421152969752189
087401966090665180351650179250461950136658543663271254963990854914420001457476081930221206602433009641270489439039717719518069908699860663658323227870
937650226014929101151717763594460202324930028040186772391028809786660565118326004368850881715723866984224220102495055188169480322100251542649463981287
367765892768816359831247788652014117411091360116499507662907794364600585194199856016264790761532103872755712699251827568798930276176114616254935649590
379804583818232336861201624373656984670378585330527583333793990752166069238053369887956513728559388349989470741618155012539706464817194670834819721448
889879067650379590366967249499254527903372963616265897603949857674139735944102374432970935547798262961459144293645142861715858733974679189757121195618
738578364475844842355558105002561149239151889309946342841393608038309166281881150371528496705974162562823609216807515017772538740256425347087908913729
172282861151591568372524163077225440633787593105982676094420326192428531701878177296023541306067213604600038966109364709514141718577701418060644363681
546444005331608778314317444081194942297559931401188868331483280270655383300469329011574414756313999722170380461709289457909627166226074071874997535921
275608441473782330327033016823719364800217328573493594756433412994302485023573221459784328264142168487872167336701061509424345698440187331281010794512
722373788612605816566805371439612788873252737389039289050686532413806279602593038772769778379286840932536588073398845721874602100531148335132385004782
716937621800490479559795929059165547050577751430817511269898518840871856402603530558373783242292418562564425502267215598027401261797192804713960068916
382866527700975276706977703643926022437284184088325184877047263844037953016690546593746161932384036389313136432713768884102681121989127522305625675625
470172508634976536728860596675274086862740791285657699631378975303466061666980421826772456053066077389962421834085988207186468262321508028828635974683
965435885668550377313129658797581050121491620765676995065971534476347032085321560367482860837865680307306265763346977429563464371670939719306087696349
532884683361303882943104080029687386911706666614680001512114344225602387447432525076938707777519329994213727721125884360871583483562696166198057252661
220679754062106208064988291845439530152998209250300549825704339055357016865312052649561485724925738620691740369521353373253166634546658859728665945113
644137033139367211856955395210845840724432383558606310680696492485123263269951460359603729725319836842336390463213671011619282171115028280160448805880
238203198149309636959673583274202498824568494127386056649135252670604623445054922758115170931492187959271800194096886698683703730220047531433818109270
803001720593553052070070607223399946399057131158709963577735902719628506114651483752620956534671329002599439766311454590268589897911583709341937044115
512192011716488056694593813118384376562062784631049034629395002945834116482411496975832601180073169943739350696629571241027323913874175492307186245454
322203955273529524024590380574450289224688628533654221381572213116328811205214648980518009202471939171055539011394331668151582884368760696110250517100
739276238555338627255353883096067164466237092264680967125406186950214317621166814009759528149390722260111268115310838731761732323526360583817315103459
573653822353499293582283685100781088463434998351840445170427018938199424341009057537625776757111809008816418331920196262341628816652137471732547772778
348877436651882875215668571950637193656539038944936642176400312152787022236646363575550356557694888654950027085392361710550213114741374410613444554419
210133617299628569489919336918472947858072915608851039678195942983318648075608367955149663644896559294818785178403877332624705194505041984774201418394
773120281588684570729054405751060128525805659470304683634459265255213700806875200959345360731622611872817392807462309468536782310609792159936001994623
799343421068781349734695924646975250624695861690917857397659519939299399556754271465491045686070209901260681870498417807917392407194599632306025470790
177452751318680998228473086076653686685551646770291133682756310722334672611370549079536583453863719623585631261838715677411873852772292259474337378569
553845624680101390572787101651296663676445187246565373040244368414081448873295784734849000301947788802046032466084287535184836495919508288832320652212
810419044804724794929134228495197002260131043006241071797150279343326340799596053144605323048852897291765987601666781193793237245385720960758227717848
336161358261289622611812945592746276713779448758675365754486140761193112595851265575973457301533364263076798544338576171533346232527057200530398828949
903425956623297578248873502925916682589445689465599265845476269452878051650172067478541788798227680653665064191097343452887833862172615626958265447820
567298775642632532159429441803994321700009054265076309558846589517170914760743713689331946909098190450129030709956622662030318264936573369841955577696
378762491885286568660760056602560544571133728684020557441603083705231224258722343885412317948138855007568938112493538631863528708379984569261998179452
336408742959118074745341955142035172618420084550917084568236820089773945584267921427347756087964427920270831215015640634134161716644806981548376449157
390012121704154787259199894382536495051477137939914720521952907939613762110723849429061635760459623125350606853765142311534966568371511660422079639446
662116325515772907097847315627827759878813649195125748332879377157145909106484164267830994972367442017586226940215940792448054125536043131799269673915
754241929660731239376354213923061787675395871143610408940996608947141834069836299367536262154524729846421375289107988438130609555262272083751862983706
678722443019579379378607210725427728907173285487437435578196651171661833088112912024520404868220007234403502544820283425418788465360259150644527165770
004452109773558589762265548494162171498953238342160011406295071849042778925855274303522139683567901807640604213830730877446017084268827226117718084266
433365178000217190344923426426629226145600433738386833555534345300426481847398921562708609565062934040526494324426144566592129122564889356965500915430
642613425266847259491431423939884543248632746184284665598533231221046625989014171210344608427161661900125719587079321756969854401339762209674945418540
711844643394699016269835160784892451405894094639526780735457970030705116368251948770118976400282764841416058720618418529718915401968825328930914966534
575357142731848201638464483249903788606900807270932767312758196656394114896171683298045513972950668760474091542042842999354102582911350224169076943166
857424252250902693903481485645130306992519959043638402842926741257342244776558417788617173726546208549829449894678735092958165263207225899236876845701
782303809656788311228930580914057261086588484587310165815116753332767488701482916741970151255978257270740643180860142814902414678047232759768426963393
577354293018673943971638861176420900406866339885684168100387238921448317607011668450388721236436704331409115573328018297798873659091665961240202177855
88548761761619893707943800566633648843650891448055710397652146960276625835990')
GO

-- select * from google_challenge

-- Find and remove decimal from e

DECLARE @PTR binary(16)
DECLARE @IDX int

select	@PTR = textptr(e),
	@IDX = charindex('.', e)-1
from 	google_challenge 
where 	e 
like 	'%.%'

-- make the change

updatetext google_challenge.e @PTR @IDX 1 ''
go

-- Loop through e, trying to find first 10 digit prime

declare @pos bigint
declare @google varchar(20)

set @pos = 1
set @google = ''

while @google <> 'prime'
begin
 select @google = dbo.is_prime(substring(e, @pos, 10)) from google_challenge
 set @pos=@pos+1
end
select @google, @pos-1, substring(e, @pos-1, 10) from google_challenge
go

Hopefully corey can come up with his method of calculating e to n precision, rather than the cheat that I had to use (thanks wikipedia).

-ec

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-15 : 21:33:47

just thought it would be twice as fast as it would skip all of the evens... I'll see if I can't get 'e' generated to at least 4000 characters...

Corey

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-16 : 00:04:29

ok... this is where i'm at:


	Declare @x decimal(38,37),
		@y decimal(38,37),
		@z int,
		@pos int,
		@e nvarchar(4000),
		@shift int

Set @e = '2.'

Set @x = 0
Set @y = 1
Set @z = 2

Set @pos = 3

Select z = @z, y = @y, x = @x, e = @e
While (@z < 85)
Begin

	Select 
		@shift = power(10,floor(power(2,-((@z+2)%3)))),
		@x = (@x + @y/@z)*@shift - convert(int,(@x + @y/@z)), 
		@y = @y*@shift/@z, 
		@e = @e + case when @shift=10 then convert(nvarchar,floor(@x)) else '' end, 
		@z = @z + 1
	
	Select z = @z, y = @y, x = @x, e = @e, shift = @shift
End
Select @e

This breaks with z>=85...

I will pick it up tommorrow... night!

Corey

jhermiz

3564 Posts

Posted - 2004-07-16 : 08:05:11

You guys are doing too much work... first you may want to reread the problem...
My blog is sort of down but sort of up...trying to switch servers.

You wont need that many characters / digits
http://www.thecenturoncompany.com/jhermiz/blog/index.html
first see that the first 10 digits after 2. make f(1)...

My blog has clues!
But for some reason the code I posted doesnt show up on the URL (server down???)

Jon
www.web-impulse.com

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-07-16 : 08:35:21

quote:
SELECT @factorial = dbo.calcfactorial (@previous_number) -- Recursive call

Why do people do this? There is absolutely nothing to be gained by using recursion to calculate factorials in procedural language.

jhermiz

3564 Posts

Posted - 2004-07-16 : 08:37:30

Why are people calculating the factorial though ?
e has already been calculated for us years and years ago.

Jon
www.web-impulse.com

Kristen
Test

22859 Posts

Posted - 2004-07-16 : 08:51:14

I'm sure you should be using a TALLY table ... :)

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-16 : 09:10:19

Jon - I think you are missing the point...

quote:

this would make a good programming challenge here. I would like to see an all SQL solution to this.

While I realize that once you have e it is extremely easy to find the first 10-digit prime. What is more difficult is to generate e to a given number of digits in SQL alone. Especially when precision seems to get a bit screwed when you get past 38 digits. That said, I thought I had figured it out late last night, but its still not quite right.

current code


Declare @x decimal(38,27),
	@y decimal(38,27),
	@z int,
	@e nvarchar(4000),
	@shift int

	Set @e = '2.'
	
	Set @x = 0
	Set @y = 1
	Set @z = 2
	
	Select z = @z, y = @y, x = @x, e = @e
	While (@z < 32)
	Begin
		Select 
			--@shift = power(10,floor(power(2,-((@z+2)%3)))),
			@shift = power(10,patindex('%00[1-9]%',right(@y,len(@y)-2))),
			@e = @e + case when @shift>1 then convert(nvarchar,convert(int,(@x + @y/@z)*@shift)) else '' end, 
			@x = (@x + @y/@z)*@shift - convert(int,(@x + @y/@z)*@shift), 
			@y = @y*@shift/@z, 
			@z = @z + 1
	
		Select z = @z, y = @y, x = @x, e = @e, shift = @shift
	End
	Select @e

Still doesn't work though... damn

Corey

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-07-16 : 09:29:58

quote:
Originally posted by Kristen

I'm sure you should be using a TALLY table ... :)

What, as part of a spigot algorithm solution? Yeah, that might work.

jhermiz

3564 Posts

Posted - 2004-07-16 : 09:33:04

ehhh

just remember though..you don't need to check numbers that are not divisible by Rad(n)
in addition, the most you need to loop is from 2 to Rad(n) for any given n. I don't know enough SQL but I use the C++ mod operator % to return a remainder..if no remainder is returned you've realized that the number is not prime.

Jon
www.web-impulse.com

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-16 : 09:58:56

whats rad(n)???
I would have thought 2 to ceiling(sqrt(n)) would be the range

Corey

jhermiz

3564 Posts

Posted - 2004-07-16 : 10:04:04

Rad(n) is just radical.
I've always been taught its a "radical" (square root) :)

Jon
www.web-impulse.com

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-07-16 : 10:09:16

ahhh... so they are the same. Thats what ec did in his solution with the pregenerated e...

now if could only get my generator to work...*sigh*... must actually work though

Oh, and I'll have a project for you shortly

Corey

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources