Coding: Hacks and Snippets

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Coding: Hacks and Snippets

Postby evilbeanfiend » Wed Jan 27, 2010 10:13 pm UTC

stephentyrone wrote:Taylor series are a bad choice for computationally approximating most functions...


however the 1st term is a pretty handy approximation for sin(x) where x is small
in ur beanz makin u eveel

Posi
Posts: 111
Joined: Mon Jul 16, 2007 6:08 am UTC

Re: Coding: Hacks and Snippets

Postby Posi » Wed Jan 27, 2010 10:43 pm UTC

TheChewanater wrote:Because I didn't even realize that...

Either way, you are a horrible person.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Coding: Hacks and Snippets

Postby TheChewanater » Thu Jan 28, 2010 2:53 am UTC

Posi wrote:
TheChewanater wrote:Because I didn't even realize that...

Either way, you are a horrible person.

...Why? Is that bad coding? Like I care...
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

Posi
Posts: 111
Joined: Mon Jul 16, 2007 6:08 am UTC

Re: Coding: Hacks and Snippets

Postby Posi » Thu Jan 28, 2010 6:54 am UTC

TheChewanater wrote:
Posi wrote:
TheChewanater wrote:Because I didn't even realize that...

Either way, you are a horrible person.

...Why? Is that bad coding? Like I care...

Its so unclear! It burns my senses just reading about it.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Coding: Hacks and Snippets

Postby Cosmologicon » Thu Jan 28, 2010 1:19 pm UTC

Would you accept a compromise?

Code: Select all

x += (right ? 1 : 0) - (left ? 1 : 0);

That's pretty clear, right? No booleans were treated arithmetically in the making of this expression.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Thu Jan 28, 2010 1:37 pm UTC

Posi wrote:
TheChewanater wrote:
Posi wrote:
TheChewanater wrote:Because I didn't even realize that...

Either way, you are a horrible person.

...Why? Is that bad coding? Like I care...

Its so unclear! It burns my senses just reading about it.


How is that unclear? Any civilized person should know that in C and family, 'bool' is just a fancy way of saying 'int'.

Cosmologicon wrote:Would you accept a compromise?

Code: Select all

x += (right ? 1 : 0) - (left ? 1 : 0);

That's pretty clear, right? No booleans were treated arithmetically in the making of this expression.


This is one of those damned if you do, damned if you don't-type scenarios. If you use booleans arithmetically, Java programmers will send the code to thedailwtf. If you do what you just did, C programmers will send your code to thedailywtf.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
rrwoods
Posts: 1509
Joined: Mon Sep 24, 2007 5:57 pm UTC
Location: US

Re: Coding: Hacks and Snippets

Postby rrwoods » Thu Jan 28, 2010 2:52 pm UTC

You, sir, name? wrote:This is one of those damned if you do, damned if you don't-type scenarios. If you use booleans arithmetically, Java programmers will send the code to thedailwtf. If you do what you just did, C programmers will send your code to thedailywtf.

Dumb Java programmers will. I'm a Java programmer. When in Rome, do as the Romans. If you can't read idiomatic C, then you have no right to complain about clarity until you learn idiomatic C.

/2c
31/M/taken/US
age/gender/interest/country

Belial wrote:The sex card is tournament legal. And I am tapping it for, like, six mana.

Posi
Posts: 111
Joined: Mon Jul 16, 2007 6:08 am UTC

Re: Coding: Hacks and Snippets

Postby Posi » Fri Jan 29, 2010 7:22 am UTC

You, sir, name? wrote:
Posi wrote:
TheChewanater wrote:
Posi wrote:
TheChewanater wrote:Because I didn't even realize that...

Either way, you are a horrible person.

...Why? Is that bad coding? Like I care...

Its so unclear! It burns my senses just reading about it.


How is that unclear? Any civilized person should know that in C and family, 'bool' is just a fancy way of saying 'int'.

Because you have to think about what that code does. The if/else style may not be pretty, but you know right away what it does.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Coding: Hacks and Snippets

Postby TheChewanater » Fri Jan 29, 2010 8:39 pm UTC

Posi wrote:
You, sir, name? wrote:
Posi wrote:
TheChewanater wrote:
Posi wrote:
TheChewanater wrote:Because I didn't even realize that...

Either way, you are a horrible person.

...Why? Is that bad coding? Like I care...

Its so unclear! It burns my senses just reading about it.


How is that unclear? Any civilized person should know that in C and family, 'bool' is just a fancy way of saying 'int'.

Because you have to think about what that code does. The if/else style may not be pretty, but you know right away what it does.

Yeah, probably. The reason I made that was because I realize that bools could be used arithmetically like ints, and not just the other way around.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Coding: Hacks and Snippets

Postby 0xBADFEED » Sat Feb 20, 2010 4:32 pm UTC

Ok, so I was just thinking the other day how ugly casting is in C++ and the ridiculous redundancy of things like:

Code: Select all

SomeObjectType* object = dynamic_cast<SomeObjectType*>(anotherObject);

So I made this little utility function to alleviate the redundancy and use the automatic C++ type deduction to fill in the appropriate types:

Code: Select all

namespace impl  {
   template <typename T> struct AutocastImpl
   {
      AutocastImpl(T* ptr):
         _ptr(ptr)
      {}

      template<typename U> operator U* ()
      {
         return dynamic_cast<U*>(_ptr);
      }

      T* _ptr;
   };
}

template<typename T>
impl::AutocastImpl<T> autocast(T* ptr)
{
   return impl::AutocastImpl<T>(ptr);
}

So it allows you to write casts like:

Code: Select all

SomeObjectType* object = autocast(anotherObject);

So obviously this little proof-of-concept only supports dynamic-cast of pointers but it would be trivial to extend it to support automatic static casting or any other 3rd-party cast routines and references in addition to pointers. Does something like this already exist? I don't immediately see any down-sides to it (other than it's non-standard and a possibly very mild performance hit) but I'm not really sure I'd ever use it in any real code. It's just such an easy utility and it seems like it cleans up casting code significantly. I'd be surprised if it doesn't already exist somewhere. Thoughts?

Also, spare me any "you shouldn't be casting blah, blah, blah" sometimes it is unavoidable, especially when using 3rd party libraries.

User avatar
Area Man
Posts: 256
Joined: Thu Dec 25, 2008 8:08 pm UTC
Location: Local

Re: Coding: Hacks and Snippets

Postby Area Man » Sat Feb 20, 2010 6:34 pm UTC

0xBADFEED wrote:So obviously this little proof-of-concept only supports dynamic-cast of pointers but it would be trivial to extend it to support automatic static casting or any other 3rd-party cast routines and references in addition to pointers. Does something like this already exist? I don't immediately see any down-sides to it (other than it's non-standard and a possibly very mild performance hit) but I'm not really sure I'd ever use it in any real code. It's just such an easy utility and it seems like it cleans up casting code significantly. I'd be surprised if it doesn't already exist somewhere. Thoughts?

C++0x :

Code: Select all

auto *object = dynamic_cast<SomeObjectType*>(anotherObject);
Bisquick boxes are a dead medium.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Coding: Hacks and Snippets

Postby 0xBADFEED » Sat Feb 20, 2010 7:04 pm UTC

Area Man wrote:C++0x :

Code: Select all

auto *object = dynamic_cast<SomeObjectType*>(anotherObject);

Yeah, I'm aware of the 'auto' declaration for C++0x and you're dead-on that's basically what I was going for.

I was more wondering if there were any existing implementations (for current standard C++) of this pattern. It's so simple and (at least to me) visually more appealing/convenient and I fail to see any serious downsides. But C++ already has enough TMTOWTDI problems when it comes to syntactic conventions. If it was a common idiom in some library or something it would assuage my misgivings a bit. I've never seen it before, personally, which leads me to think it probably isn't. The general strategy is used pretty frequently, iirc Boost.Assign uses a similar pattern for conversion from intermediate storage to the actual population of concrete containers.

I doubt I would ever use it in any real code as the problem it's solving isn't very compelling and it's much less useful than the 'auto' keyword (and C++0x will have more widespread support eventually). It was just something I thought was kind of neat.

User avatar
Area Man
Posts: 256
Joined: Thu Dec 25, 2008 8:08 pm UTC
Location: Local

Re: Coding: Hacks and Snippets

Postby Area Man » Sat Feb 20, 2010 9:45 pm UTC

The new auto has been useful since gcc 4.4 (using -std=c++0x), and it won't be taken out of the standard, so I use it now.

If I recall correctly, the static/dynamic/const/reinterpret_cast notation was deliberately made explicit and "ugly" to be easier to spot in code than c-style casts (but I can't find a reference for it). Making it easy for a user to hide this kind of thing is contrary to that, and probably a bad thing.

Code: Select all

// imo, don't do something like this...
#define DCAST( x, y, z ) x* y = dynamic_cast<x*>(z)

  // ...in code, looks like a function, isn't.
  DCAST( SomeObjectType, object, anotherObject );

Convenient, maybe; camouflaged, yes. Shouldn't be done often enough to warrant it.

But (your function's) a neat exercise for templating, nonetheless.
Bisquick boxes are a dead medium.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Coding: Hacks and Snippets

Postby 0xBADFEED » Sat Feb 20, 2010 11:56 pm UTC

Area Man wrote:The new auto has been useful since gcc 4.4 (using -std=c++0x), and it won't be taken out of the standard, so I use it now.

Yeah I know, but I tend to use VC8 so no love for me on the 0x front.
If I recall correctly, the static/dynamic/const/reinterpret_cast notation was deliberately made explicit and "ugly" to be easier to spot in code than c-style casts (but I can't find a reference for it). Making it easy for a user to hide this kind of thing is contrary to that, and probably a bad thing.

Yeah I have heard this as well. I'm just not really sure I agree with it. I violate it on a fairly frequent basis. I already side-step const_cast when I have to using a utility along the lines of:

Code: Select all

template<typename T> T* unconst(const T* v) { return const_cast<T*>(v);}

When you're dealing with libraries that expect non-const c-style strings const_cast starts to get pretty tedious. And I tend to prefer the 'unconst' rather than a specific C-style cast (or const_cast) since if the type of the affected variable changes the unconst-ing semantics remain intact with the templated function but not so with an explicit C-style cast.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Coding: Hacks and Snippets

Postby TheChewanater » Sun Feb 21, 2010 4:46 am UTC

I just made a teeny tiny shell script called "fixapt" that removes the lock file in a symbolic link to /etc/dpkg/lib/ owned my my non-root account. It's the shortest and most useful shell script I've ever written. Even better than the one I wrote today that runs on the cRIOs in F.I.R.S.T. robots sends viruses to all the other robots on the same network.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
lulzfish
Posts: 1214
Joined: Tue Dec 16, 2008 8:17 am UTC

Re: Coding: Hacks and Snippets

Postby lulzfish » Sun Feb 21, 2010 7:37 am UTC

Somewhere, I have a shell script called "crack". It is extremely useful, but only for a few seconds in some cases, and it would be more useful if Dolphin implemented it.

Have you ever downloaded one of those zips that has like a billions nested folders?
You get "sauce.zip".
You unzip it.
You go into the directory "sauce".
You go into the directory "src".
You go into the directory "2010-02-21".
You go into the directory "source".
HEY! There's the file I wanted! Fucking 4 levels in!

crack.sh is a simple script that 'cracks' open directories like coconuts, to acquire the delicious innards faster. It automatically moves everything out of a directory, then deletes the empty directory. Unfortunately, I don't know anything about permissions, and it's only useful every once in a while, so I've not developed it. But it seems like the kind of "duh" thing that should obviously be standard in all file managers. Like "Up" and like not having those stupid bread-crumbs. I should just write my own file manager.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Coding: Hacks and Snippets

Postby TheChewanater » Sun Feb 21, 2010 7:57 am UTC

lulzfish wrote:Somewhere, I have a shell script called "crack". It is extremely useful, but only for a few seconds in some cases, and it would be more useful if Dolphin implemented it.

Have you ever downloaded one of those zips that has like a billions nested folders?
You get "sauce.zip".
You unzip it.
You go into the directory "sauce".
You go into the directory "src".
You go into the directory "2010-02-21".
You go into the directory "source".
HEY! There's the file I wanted! Fucking 4 levels in!

crack.sh is a simple script that 'cracks' open directories like coconuts, to acquire the delicious innards faster. It automatically moves everything out of a directory, then deletes the empty directory. Unfortunately, I don't know anything about permissions, and it's only useful every once in a while, so I've not developed it. But it seems like the kind of "duh" thing that should obviously be standard in all file managers. Like "Up" and like not having those stupid bread-crumbs. I should just write my own file manager.


I really could have used that a few hours ago. Hey, mind posting it?
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
lulzfish
Posts: 1214
Joined: Tue Dec 16, 2008 8:17 am UTC

Re: Coding: Hacks and Snippets

Postby lulzfish » Sun Feb 21, 2010 8:18 am UTC

Code: Select all

#!/bin/bash
# I'll get back to this later. It's a tool for cracking directories open.

if [ -d "$1" ]; then
        mv $1/* $1/..
        rmdir $1
else
        echo "Argument should be a directory"
fi

It probably doesn't preserve permissions or anything. It's just an automated "mv * ; rmdir". Obviously.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Coding: Hacks and Snippets

Postby TheChewanater » Sun Feb 21, 2010 8:23 am UTC

lulzfish wrote:

Code: Select all

#!/bin/bash
# I'll get back to this later. It's a tool for cracking directories open.

if [ -d "$1" ]; then
        mv $1/* $1/..
        rmdir $1
else
        echo "Argument should be a directory"
fi

It probably doesn't preserve permissions or anything. It's just an automated "mv * ; rmdir". Obviously.

*facepalm* Wow, I didn't think it would be that simple.

Well, that's added to my collection of miscellaneous utility scripts.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Coding: Hacks and Snippets

Postby Ended » Thu Feb 25, 2010 1:38 pm UTC

Snippet time! I wanted an easy way to embed documentation in my bash script (in a similar way to how Doxygen works, although obviously much simpler):

Code: Select all

#!/bin/bash
function print_documentation
{
  ##!         Here's some documentation!
  identifier=$1
  # There's one space and one tab between all the square brackets below
  searchstring="^[      ]*$identifier"
  grep "$searchstring" $0 | sed "s/^[    ]*$identifier[  ]*//"
}

#£ Here's some different documentation... #£ ##!

print_documentation $1

Usage:

Code: Select all

$ ./tmp.sh '##!'
Here's some documentation!
$ ./tmp.sh '#£'
Here's some different documentation... #£ ##!
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Coding: Hacks and Snippets

Postby Dr. Willpower » Mon Mar 01, 2010 8:56 pm UTC

This is not much of an accomplishment, but I've been trying to figure out how to sqrt() without google for over a month.

The algorithm I wrote:

Code: Select all

double sqrt(double toberooted, double guess){

        double y = toberooted / guess;
       
        if (y == guess){

                return guess;

        }

        guess = (guess + y) / 2;
        return sqrt(toberooted, guess);

}
Image
Hat me, bro

User avatar
Yakk
Poster with most posts but no title.
Posts: 11083
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Mon Mar 01, 2010 9:12 pm UTC

Code: Select all

double invert_internal( function<double(double)> f, double target, double a, double b )
{
   double test = 0.;
   double middle = 0.;
   do
   {
      middle = (a+b)/2.;
      if (middle == a) return middle;
      test = f((a+b)/2.);
      if (test < target)
      {
         a = middle;
         continue;
      }
      if (test > target)
      {
         b = middle;
         continue;
      }
   } while (test != target)

   return middle;
}

double invert_monotonic_function( function<double(double)> f, double target )
{
   double a = 0.;
   double interval = 1.;
   while (f(a) > target)
   {
      a += interval;
      interval *= -2.;
   }
   double b = 0.;
   interval = 1.;
   while (f(b) < target)
   {
      b += interval;
      interval *= -2.;
   }
   return invert_internal( f, target, a, b );
}

I think that is a generalisation of your "find square root"? Pass it a function that squares its input, and it will return the square root of it.

It should work on most reasonably sane, reasonably continuous functions that are monotonic. The monotonic part is a requirement so the first function can automatically find a seed interval to search in (a,b).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
RoadieRich
The Black Hand
Posts: 1037
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Behind you

Re: Coding: Hacks and Snippets

Postby RoadieRich » Mon Mar 01, 2010 10:14 pm UTC

Dr. Willpower wrote:This is not much of an accomplishment, but I've been trying to figure out how to sqrt() without google for over a month.

The algorithm I wrote:

Code: Select all

double sqrt(double toberooted, double guess){

        double y = toberooted / guess;
       
        if (y == guess){

                return guess;

        }

        guess = (guess + y) / 2;
        return sqrt(toberooted, guess);

}

Is this guaranteed to terminate? I've been unable to find a case in which it won't (not that I've looked very hard), but doing == on two floats always seems risky to me.
73, de KE8BSL loc EN26.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Mon Mar 01, 2010 10:20 pm UTC

Yeah, that's an integer algorithm. For floats, there needs to be some form of termination condition.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Hacks and Snippets

Postby Berengal » Mon Mar 01, 2010 11:06 pm UTC

I quite like this one as a relatively quick-n-dirty square root:

Code: Select all

derive ε f = \x → (f (x + ε) - f x) / ε

newton ε f = newt
  where
    f' = derive ε f
    newt x | abs (f x) < ε = x
           | otherwise = newt x'
      where
        x' = x - (f x / f' x)

squareRoot x = newton ε (\x' → x'^2 - x) 0
  where ε = 0.00001
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Mon Mar 01, 2010 11:18 pm UTC

I would

Code: Select all

squareRoot x eps = last $ takeWhile test $ iterate f (x/2)
  where
    f guess = (guess + x / guess) / 2
    test guess = abs(x - guess^2) > eps^2


Granted, it's a different algorithm, and less general.


--edit--

Though I think it may not always halt. Hmm.

Substantially less pretty version that always halts:

--edit--

Code: Select all

squareRoot x eps =  fst $ last $ takeWhile diffTest $ split $ takeWhile test $ iterate f (x/2)
  where
    f guess = (guess + x / guess) / 2
    test guess = abs(x - guess^2) > eps^2
    split a = zipWith (,) a $ tail a
    diffTest (a,b) = a /= b
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Coding: Hacks and Snippets

Postby headprogrammingczar » Tue Mar 02, 2010 1:02 am UTC

Berengal wrote:I quite like this one as a relatively quick-n-dirty square root:

Code: Select all

derive ε f = \x → (f (x + ε) - f x) / ε

newton ε f = newt
  where
    f' = derive ε f
    newt x | abs (f x) < ε = x
           | otherwise = newt x'
      where
        x' = x - (f x / f' x)

squareRoot x = newton ε (\x' → x'^2 - x) 0
  where ε = 0.00001

What language is that?
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Tue Mar 02, 2010 1:10 am UTC

headprogrammingczar wrote:
Berengal wrote:I quite like this one as a relatively quick-n-dirty square root:

Code: Select all

derive ε f = \x → (f (x + ε) - f x) / ε

newton ε f = newt
  where
    f' = derive ε f
    newt x | abs (f x) < ε = x
           | otherwise = newt x'
      where
        x' = x - (f x / f' x)

squareRoot x = newton ε (\x' → x'^2 - x) 0
  where ε = 0.00001

What language is that?


Haskell. Leksah (et al.?) renders it that way. It's like APL, except it's reasonably readable.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Coding: Hacks and Snippets

Postby TheChewanater » Tue Mar 02, 2010 1:31 am UTC

You, sir, name? wrote:
headprogrammingczar wrote:
Berengal wrote:I quite like this one as a relatively quick-n-dirty square root:

Code: Select all

derive ε f = \x → (f (x + ε) - f x) / ε

newton ε f = newt
  where
    f' = derive ε f
    newt x | abs (f x) < ε = x
           | otherwise = newt x'
      where
        x' = x - (f x / f' x)

squareRoot x = newton ε (\x' → x'^2 - x) 0
  where ε = 0.00001

What language is that?

Haskell. Leksah (et al.?) renders it that way. It's like APL, except it's reasonably readable.

Readable? Yes. But, writable?
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Tue Mar 02, 2010 2:02 am UTC

TheChewanater wrote:
You, sir, name? wrote:
headprogrammingczar wrote:
Berengal wrote:I quite like this one as a relatively quick-n-dirty square root:

Code: Select all

derive ε f = \x → (f (x + ε) - f x) / ε

newton ε f = newt
  where
    f' = derive ε f
    newt x | abs (f x) < ε = x
           | otherwise = newt x'
      where
        x' = x - (f x / f' x)

squareRoot x = newton ε (\x' → x'^2 - x) 0
  where ε = 0.00001

What language is that?

Haskell. Leksah (et al.?) renders it that way. It's like APL, except it's reasonably readable.

Readable? Yes. But, writable?


No more difficult to write than regular haskell. If you (to borrow some of Berengal's code) write

Code: Select all

derive epsilon f = \x -> (f (x + epsilon) - f x) / epsilon

It converts to

Code: Select all

derive ε f = \x → (f (x + ε) - f x) / ε

on the fly.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Coding: Hacks and Snippets

Postby stephentyrone » Tue Mar 02, 2010 2:47 am UTC

That's an awful lot of work to do something that's a single instruction on essentially all modern hardware. I thought high-level languages were supposed to let you do more with less code? :D

Aside: Generally, when you use Newton-Raphson iteration to compute square roots, you iterate on a reciprocal square root estimate (that is, if you want the square root of S, start by finding the zero of f(x) = x^-2 - S). This is used because it lets you avoid doing any divisions in the course of the algorithm. Each Newton-Raphson step is just:
[math]x_{n+1} = x_n - \frac{x_n^{-2} - S}{-2x_n^{-3}} = x_n\left(\frac32 - \frac12Sx_n^{2}\right)[/math]
Note that the correction factor is the first-order (in Sx^2) Taylor approximation to the ratio of the actual reciprocal square root and the current guess; one can use a higher-order approximation -- or a different approximation, like a Chebyshev or Minimax polynomial, or a Padé approximation -- to get better convergence.

What's also nice about this approach is that nearly all hardware (even ARM) has a fast reciprocal square root estimate instruction for exactly this purpose.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

fazzone
Posts: 186
Joined: Wed Dec 10, 2008 9:38 pm UTC
Location: A boat

Re: Coding: Hacks and Snippets

Postby fazzone » Tue Mar 02, 2010 3:15 am UTC

Or you could use http://en.wikipedia.org/wiki/Fast_inverse_square_root (Probably less efficient, but entertaining anyway)
*/

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Coding: Hacks and Snippets

Postby Dr. Willpower » Tue Mar 02, 2010 3:22 am UTC

RoadieRich wrote:
Dr. Willpower wrote:This is not much of an accomplishment, but I've been trying to figure out how to sqrt() without google for over a month.

The algorithm I wrote:

Code: Select all

double sqrt(double toberooted, double guess){

        double y = toberooted / guess;
       
        if (y == guess){

                return guess;

        }

        guess = (guess + y) / 2;
        return sqrt(toberooted, guess);

}

Is this guaranteed to terminate? I've been unable to find a case in which it won't (not that I've looked very hard), but doing == on two floats always seems risky to me.


I meant it only as a proof of concept. It may have unexpected behavior. Although, you could develop your own rounding algorithm and tack on a few lines of code?
Image
Hat me, bro

User avatar
phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Tue Mar 02, 2010 4:28 am UTC

I've always found it odd that, for examples like this, we'll still use a numeric approximate-derivative calculation, even for things like x2, when we know the correct derivative. Why must we sacrifice accuracy in the name of genericity?

So I threw this together quickly:

Code: Select all

class DerivableFunc f where
   evaluate :: (Fractional x) => f x x -> x -> x
   derivative :: (Fractional x) => x -> f x x -> f x x

newtonSolve :: (Ord x, Fractional x, DerivableFunc f) => x -> f x x -> x -> x
newtonSolve epsilon f y = solve y -- y is as good a starting guess as anything
   where solve guess
      | abs (guess_val - y) <= epsilon = guess
      | otherwise = solve (guess - (guess_val - y) / guess_slope)
      where guess_val = evaluate f guess
            guess_slope = evaluate (derivative 0.1 f) guess

-- So then you could do:
instance DerivableFunc (->) where
   -- evaluate :: (Fractional x) => (x -> x) -> (x -> x) -- pretty simple
   evaluate = id
   -- derivative :: (Fractional x) => x -> (x -> x) -> (x -> x)
   derivative epsilon f x = (f (x + epsilon) - f (x - epsilon)) / (2 * epsilon)

sqrt_1 = newtonSolve 0.001 (^2)

-- Or you could do:
data Polynomial x y = Polynomial [x] -- Polynomial [a,b,c,d,...] encapsulates a + bx + cx^2 + dx^3 + ...
instance DerivableFunc Polynomial where
   -- evaluate :: (Fractional x) => Polynomial x -> x -> x
   evaluate (Polynomial cs) x = sum $ map (uncurry (*)) $ zip cs $ iterate (*x) 1
   -- evaluate :: (Fractional x) => x -> Polynomial x -> Polynomial x
   -- we can ignore epsilon, 'cause we can get the exact answer
   derivative _ (Polynomial []) = Polynomial []
   derivative _ (Polynomial cs) = Polynomial $ map (uncurry (*)) $ zip (map fromIntegral [1..]) (tail cs)

sqrt_2 = newtonSolve 0.001 (Polynomial [0,0,1])


But a couple of points:
(a) Square roots are a pretty poor example here, since that particular derivative approximation actually gives the correct result... so sqrt_1 and sqrt_2 actually return the same answers (modulo some rounding errors). But still, it's the principle, dammit!
(b) Is there a better way to say "all x->x functions are instances of this class" than that? The way it's written, it requires all DerivableFunc instances to be of the form "f x x"... which makes the Polynomial definition uglier. Basically, I want some kind of (\f x -> f x x), except for types, that I can apply to (->) for its definition.
(c) It'd be nice if the function returned by derivative could be a different kind of DerivableFunc than the input... but I don't think that's possible with Haskell's type system... rambling stream-of-consciousness behind the spoiler.
Spoiler:
The idea being so we could take some horrible function, make a type to encapsulate that horrible function, and return its derivative as a normal function, so if you try to take the second derivative it'll use the numerical method... rather than having to somehow generically encapsulate every level of differentiation into a single object, like Polynomial does.
It could also move the numeric differentiation code into DerivableFunc itself as a default... like, if you override derivative, you can calculate it however you want, but if you don't override it, it'll do it numerically.

Playing around, I tried something like:

Code: Select all

class DerivableFunc f g where
   evaluate :: (Fractional x) => f x x -> x -> x
   derivative :: (Fractional x) => x -> f x x -> g x x

instance DerivableFunc (->) (->) where etc
instance DerivableFunc Polynomial Polynomial where etc
instance DerivableFunc HorribleFunction (->) where etc
and that let me declare the types at least, but it's no good... Firstly, you need to turn on some kind of extra feature in ghc to do any of this, so I presume the Haskell spec doesn't actually allow it.
Also, you try to do, say, "evaluate (derivative 0.001 (^2)) x", and it doesn't know it's supposed to use derivative::x->(x->x)->(x->x), instead of some other derivative::x->(x->x)->g x x, even though there's no instance for the latter (in fact, the error message complains that there's no generic "DerivableFunc (->) g" instance). And thinking about it, this does make perfect sense... the way it's defined, there can be several instances of DerivableFunc with the same f, but different g's. Worse, evaluate is left floating entirely... you could define the types exactly when you call it, and g is still left floating around... you can fix this by separating evaluate and derive into separate classes:

Code: Select all

class Func f where
   evaluate :: (Fractional x) => f x x -> x -> x
class (Func f, Func g) => DerivableFunc f g where
   derivative :: (Fractional x) => x -> f x x -> g x x
but that still doesn't fix the problem with derive.
What I want is some way in the instance to say that derivative on a function returns a function, derivative on a Polynomial returns a Polynomial, derivative on a HorribleFunction returns a normal function, etc... Is that possible in Haskell's type system?

I'm assuming not, because then you'd never be able to write something like:

Code: Select all

foo :: (?)
foo = derive 0.001
No type for "foo" would fit... you can't just say

Code: Select all

foo :: (Func f, Func g) => f Float Float -> g Float Float
or the like, because it'd have the same problem - you could mix and match any f and g and try to call it... and not every f and g is an instance of DerivableFunc. But anything more restrictive would go too far - not every instance of DerivableFunc would be able to be passed to foo. I guess the type of derive itself would have the same problem.
It seems sorta like I'm asking for dynamic types here... the output type is dependent on the input type instead of the input value, but it still doesn't work, for the same reason...

I suppose we could have derivative always return a normal function... so finding the second derivative will always use the numeric method, even though you can provide an exact formula for the first derivative... that's enough for Newton's method, which only uses the first derivative, but again, for the sake of genericity...

(d) It feels like I'm doing this backwards, somehow... maybe it's all those builtin types I've seen where there's a way to lift a function to a whatever, but not backwards, whereas this has the reverse... I suppose that makes sense, though... every function is an Arrow, but not vice-versa... but not every function is a DerivableFunc, but yes vice-versa.
(e) I have a vague feeling that this should be a monad. I don't know whence that feeling comes, or whether it's remotely accurate.

I suppose what I'm saying is: my Haskell code still feels like Frankenstein's monster whenever I do anything remotely fancy, and I'm probably Doing It Wrong. Good enough for the hacks thread, though.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
chridd
Has a vermicelli title
Posts: 824
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Coding: Hacks and Snippets

Postby chridd » Tue Mar 02, 2010 5:07 am UTC

phlip wrote:So I threw this together quickly:
stephentyrone wrote:I thought high-level languages were supposed to let you do more with less code? :D


As long as you're avoiding sacrifices in the name of genericity, why not do something like:

Code: Select all

squareRoot num epsilon = newt 1
  where newt x | abs (x*x-num) <= epsilon = x
               | otherwise = newt x' where x' = x - (x*x-num) / (2*x)

or, even better

Code: Select all

squareRoot num = sqrt num -- from standard library
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she(?)(?(?)(?))(?(?(?))(?))(?) · Forum game scores
mittfh wrote:I wish this post was very quotable...
flicky1991 wrote:In both cases the quote is "I'm being quoted too much!"
chridd (on Discord) wrote:
Dummy wrote:Sorry You're Gay Dads
SYG'D

User avatar
phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Tue Mar 02, 2010 5:12 am UTC

But that's sacrificing genericity in the name of brevity.

I was trying to come up with something that'd be just as general, but without the sacrifices where they weren't necessary. Sqrt is just an example.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
chridd
Has a vermicelli title
Posts: 824
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Coding: Hacks and Snippets

Postby chridd » Tue Mar 02, 2010 5:25 am UTC

phlip wrote:But that's sacrificing genericity in the name of brevity.

I was trying to come up with something that'd be just as general, but without the sacrifices where they weren't necessary. Sqrt is just an example.
(I was not entirely serious in my previous post)

In any case, if you wanted to use exact derivatives, couldn't you just pass the derivative to the function as a separate argument? I.e., newton epsilon (^2) (*2)?
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she(?)(?(?)(?))(?(?(?))(?))(?) · Forum game scores
mittfh wrote:I wish this post was very quotable...
flicky1991 wrote:In both cases the quote is "I'm being quoted too much!"
chridd (on Discord) wrote:
Dummy wrote:Sorry You're Gay Dads
SYG'D

User avatar
phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Tue Mar 02, 2010 5:54 am UTC

'Cause Newton isn't the only thing that uses derivatives... you have to think general! Consider, with my code, you could write:

Code: Select all

taylor epsilon f = calculate f 1 1
  where calculate f n acc = (evaluate f 0) / acc : calculate (derivative epsilon f) (n + 1) (acc * n)
and get the Taylor polynomial for a function... obviously, if it's doing numeric differentiation, the coefficients will get steadily less and less accurate (for f=exp, it gets the first 4 terms correct with epsilon=1e-4, which seems to be about the best you can do... any higher, you get approximation errors, any lower, you get rounding errors), but if you pass in something that has its own derivative funtion, then it'll give you the right answer (pass in a Polynomial, and you get your original list back, followed by a bunch of zeros).

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Coding: Hacks and Snippets

Postby stephentyrone » Tue Mar 02, 2010 6:03 am UTC

fazzone wrote:Or you could use http://en.wikipedia.org/wiki/Fast_inverse_square_root (Probably less efficient, but entertaining anyway)


Yeah, sadly it turns out that the "fast" inverse square root is (a) no longer portable due to the extremely zealous adherence to aliasing rules in many current compiler optimizers, and (b) slower than just using the floating point hardware on (nearly) any computer built in the last 8 years, and even current-generation smartphones.

Re: genericness and numerical derivatives, whenever I write high-level numerics code that requires derivatives, I let the library user provide a derivative function. They can decide case-by-case whether they want to use numerical differentiation or provide exact derivatives (or some other option; I've occasionally found it useful to use a taylor series approximation to the derivative, for example)
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5097
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Coding: Hacks and Snippets

Postby Xeio » Tue Mar 02, 2010 7:57 am UTC

stephentyrone wrote:Yeah, sadly it turns out that the "fast" inverse square root is (a) no longer portable due to the extremely zealous adherence to aliasing rules in many current compiler optimizers, and (b) slower than just using the floating point hardware on (nearly) any computer built in the last 8 years, and even current-generation smartphones.
Not to mention even if both of those weren't true, it's also much less precise, which if you're really doing something where you need accuracy, you're better off with a bit slower but surer method.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests