Author 
Message 

Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 13 Feb 2007 09:49:23 pm Post subject: 


Teaser/Challenge #9
Make a program that will calculate and display the arithmeticgeometric mean
of two numbers that reside in Ans as a list of two elements. The program size
minus the number of characters in its title should end up as exactly 28 bytes.
Note: The result displayed at the end must be a number and cannot be a list.
Last edited by Guest on 02 Aug 2010 02:12:48 am; edited 1 time in total 

Back to top 


Harrierfalcon The Raptor of Calcs
Super Elite (Last Title)
Joined: 25 Oct 2006 Posts: 2535

Posted: 13 Feb 2007 09:55:48 pm Post subject: 


Umm...what exactly is a "arithmeticgeometric mean"? Obviously it's not just the average... 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 13 Feb 2007 09:57:54 pm Post subject: 


Harrierfalcon wrote: Umm...what exactly is a "arithmeticgeometric mean"? Obviously it's not just the average... Start searching, and don't ask questions before you do. :)
I'll give you two sources: Wikipedia and MathWorld.
Last edited by Guest on 13 Feb 2007 09:58:34 pm; edited 1 time in total 

Back to top 


Harrierfalcon The Raptor of Calcs
Super Elite (Last Title)
Joined: 25 Oct 2006 Posts: 2535

Posted: 13 Feb 2007 10:18:34 pm Post subject: 


Sorry.
Not even a quarter of the way there and 36 bytes. Hmm... 

Back to top 


nitacku
Advanced Member
Joined: 23 Aug 2005 Posts: 408

Posted: 13 Feb 2007 11:34:28 pm Post subject: 


Wow... had to use some calculus on this one.
My finished algorithm is 46 bytes though.
EDIT1: Saved 1 byte. Now it is 45 bytes
EDIT2: Saved 2 bytes. Now it is 43 bytes
Decided to post the code as a screenshot rather than try to type out all the symbols
Spoiler:[attachment=1311:attachment]
Last edited by Guest on 14 Feb 2007 12:14:50 am; edited 1 time in total 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 14 Feb 2007 12:29:28 am Post subject: 


Well built. :)
[EDIT]
I'm looking more at a bivariate iterative process that depends on a few builtin
instructions in some strategic locations, consisting in total of four lines of code.
Last edited by Guest on 14 Feb 2007 12:44:31 am; edited 1 time in total 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 14 Feb 2007 07:18:26 pm Post subject: 


I think I got it. If you don't mind the algorithm overflowing when one of the values is too big to be squared, you can cut it down by another byte.
spoiler wrote: While max(ΔList(Ans //or While stdDev(Ans
{mean(Ans),prod(√(Ans
End
mean(Ans
Last edited by Guest on 10 May 2008 07:41:29 pm; edited 1 time in total 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 15 Feb 2007 01:47:08 am Post subject: 


The 27 byte version, while slower, definitely wins the contest. The only other
piece that was different from mine was in the last line, where many functions
could easily act as replacements (16 in the LIST MATH submenu, mostly). :)
So, who can come up a new challenge? 

Back to top 


nitacku
Advanced Member
Joined: 23 Aug 2005 Posts: 408

Posted: 15 Feb 2007 02:24:47 am Post subject: 


<> What about mine!</> :biggrin:
It's 100% accurate according to Gauss's constant
So you mean I didn't have to do all that calculus? 

Back to top 


bfr
Member
Joined: 13 Feb 2006 Posts: 108

Posted: 15 Feb 2007 06:19:58 pm Post subject: 


I would hope that finding the arithmeticgeometric mean wouldn't require calculus. :P
luby wrote: i is sqrt(1) so if you do 3+4i it really is sqrt(3^2+4^2) The abs gets you the positive which is 5
[post="92780"]<{POST_SNAPBACK}>[/post]
I know this is an old quote, somebody might have already corrected this, but while I was reading through this thread, this just kind of stood out  it is wrong. "abs" is finding the distance from 3+4i to the origin on the realimaginary number grid. It is not there just to make the answer postive (not trying to be really picky or rude, but that really just jumped out at me). 

Back to top 


thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569

Posted: 10 May 2008 01:40:40 pm Post subject: 


A late addition, and certainly not the most compact one, but this particular algorithm for the AGM is useful when the product of the two original arguments will overflow:
(highlight below)
1→V:max(A,B→U
√(1−(min(A,B)/Ans)ē→C
While Ans
.5(V+√(Vē−Ansē→V
Cē/4/Ans→C
End
UV
(the above routine assumes that the two arguments are stored in A and B).
Appropriate modifications would of course be needed if the assumption of positive A and B is no longer valid.
thornahawk
Last edited by Guest on 10 May 2008 01:44:50 pm; edited 1 time in total 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 10 May 2008 02:12:31 pm Post subject: 


Wouldn't prod(√(Ans be a valid way to prevent the product from overflowing? Except for the use of stdDev( (which can be avoided), I don't see any way that the routine Goose and I came up with is problematic.
Of course, negative numbers are kind of annoying...
Last edited by Guest on 02 Aug 2010 02:12:35 am; edited 1 time in total 

Back to top 


WikiGuru ADOS (Attention deficit... Oh! Shiny!)
Elite
Joined: 15 Sep 2005 Posts: 923

Posted: 10 May 2008 04:11:45 pm Post subject: 


wow, for a second i thought it said calculate the arithmetic and geometric mean of two numbers, i had a program that did it in 23 bytes! hmmm... arithmeticgeometric mean... 

Back to top 


thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569

Posted: 10 May 2008 09:10:39 pm Post subject: 


After more literaturesearching, it turns out (to my chagrin! ) that still the best way to do an AGM iteration so that it reliably works for too big or too small numbers (or for that matter, complex numbers), is to use the socalled "homogeneity relation":
AGM(c*a,c*B) == c*AGM(a,B)
along with the classical a_{i+1} := (a_{i}+b_{i})/2 , b_{i+1} := √(a_{i}*b_{i}).
So your method, with that modification (whichever of A and B that has the largest magnitude is the appropriate "c"), would still beat the method I had posted. For true robustness, one would also check for the case of either one of A and B being zero, in which case the result should be zero.
On my part, I got interested in this topic again because I have had the need to write programs for computing elliptic integrals and elliptic functions, where AGMbased methods are one of the speediest.
thornahawk
P.S. ...and it turns out, in those particular applications, the actual function needed is AGM(1,√(a))!
Last edited by Guest on 10 May 2008 09:11:54 pm; edited 1 time in total 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 10 May 2008 09:51:09 pm Post subject: 


What magnitude would you want to reduce the numbers to, though? I can't think of any reason computing AGM(1,2) would be more accurate or faster than computing AGM(1000000,2000000). 

Back to top 


