advanced code snippet search

Posted By

Scooter on 01/17/09


Tagged

math


Versions (?)

Who likes this?

2 people have marked this snippet as a favorite

wizard04
umang_nine


Triangular Numbers

 / Published in: PHP
 

URL: http://reusablecode.blogspot.com/2009/01/triangular-numbers.html

Before some troll comes along and criticizes this function, bear in mind that it has legitimate uses. For example, it can be used to solve the handshake problem: how many handshakes if each person in a room full of n+1 total people shakes hands once with each other person?

Expand | Embed | Plain Text 
  1. <?php
  2.     /*
  3.     Copyright (c) 2009, reusablecode.blogspot.com; some rights reserved.
  4.     
  5.     This work is licensed under the Creative Commons Attribution License. To view
  6.     a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or
  7.     send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California
  8.     94305, USA.
  9.     */
  10.  
  11.     function triangularNumber($number)
  12.     {
  13.         for($i = 1; $i <= $number; $i++)
  14.         {
  15.             $result += $i;
  16.         }
  17.  
  18.         return $result;
  19.     }
  20. ?>

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: Omnikron13 on April 8, 2013

There is a mathematical trick that allows you to -dramatically- speed up the calculation, especially with regard to working with larger triangular numbers.

You can read about the method here: http://www.curiousmath.com/index.php?name=News&file=article&sid=95

Below is a proof demonstrating the difference in speed of these methods:

Posted By: Omnikron13 on April 8, 2013

Whoops, my code got cut...

Posted By: Omnikron13 on April 8, 2013 
<?php

function triangularNumber_1($_x) {
    for($i = 1; $i <= $_x; $i++) {
        $result += $i;
    }
    return $result;
}

/*  
 *  Due to being a simple piece of mathematics, my triangular number function is likely
 *  exempt from copyright, but just in case I eschew all copyright and give it entirely
 *  to the public domain.
 *      --Joey Sabey
 */
function triangularNumber_2($_x) {
    return (($_x / 2) + 0.5) * $_x;
}

print "Triangular number 32, method 1 - ".triangularNumber_1(32)."

"; print "Triangular number 32, method 2 - ".triangularNumber_2(32)." ";

$start = time();
for($x = 0; $x < 1000000; $x++) {
    triangularNumber_1(256);
}
print "A million passes of 256, method 1 - ".(time() - $start)." seconds

"; $start = time(); for($x = 0; $x < 1000000; $x++) { triangularNumber_2(256); } print "A million passes of 256, method 2 - ".(time() - $start)." seconds ";

?>
Posted By: Omnikron13 on April 8, 2013

Eugh, I give up with the comments on this site, you get the idea...

You need to login to post a comment.