#!/usr/bin/perl -w

# hypothesis:
# power laws come about when randomly selected numbers come from a
# scarce source. this script tests this.

use strict;

my $max_power_of_ten = 12;

my $initial_resource = 10 ** $max_power_of_ten;
my $resource_floor = $initial_resource ** -1;

my %global_buckets = ();

my $i = 0;
while(++$i < 10000) {
	my @chunks = @{&allocate_resource($initial_resource, $resource_floor)};

	#my %buckets = %{&bucket_sort(\@chunks, $max_power_of_ten)};
	#my %buckets = %{&bucket_sort2(\@chunks, $initial_resource, $resource_floor)};
	my %buckets = %{&bucket_sort3(\@chunks, $initial_resource)};

	foreach my $key ( keys %buckets) {
		$global_buckets{$key} += $buckets{$key} || 0;
	}

}

foreach my $halves ( sort { $a <=> $b } keys %global_buckets ) {
	#print $initial_resource / (2**$halves) . "\t" . $global_buckets{$halves} . "\n";
	print $halves . "\t" . $global_buckets{$halves} . "\n";
}







sub allocate_resource {
	my $resource_remaining = shift;
	my $resource_floor = shift;
	my @chunks = ();

	while($resource_remaining > $resource_floor) {
		my $chunk = rand($resource_remaining);
		push @chunks, $chunk;
		$resource_remaining -= $chunk;
	}
	
	return \@chunks;
}

sub bucket_sort {
	my $chunks_arr = shift;
	my $max_power_of_ten = shift;
	my %buckets = ();
	
	for(my $i = -$max_power_of_ten; $i < $max_power_of_ten; ++$i) {
		my $max_chunk = 10 ** $i;

		my $counter = 0;
		foreach my $chunk (@{$chunks_arr}) {
			if($chunk < $max_chunk) {
				++$counter;
			}
		}
		
		$buckets{$i} = $counter;
	}
	
	return \%buckets;
}

sub bucket_sort2 {
	my $chunks_arr = shift;
	my $initial_resource = shift;
	my $resource_floor = shift;
	my %buckets = ();
	
	my $max_quantity = $initial_resource;

	my $halves = 0;	
	while($max_quantity > $resource_floor) {
		my $min_quantity = $max_quantity / 2;

		my $counter = 0;
		foreach my $chunk (@{$chunks_arr}) {
			if($chunk > $min_quantity && $chunk <= $max_quantity) {
				++$counter;
			}
		}
		
		$buckets{$halves} = $counter;

		$max_quantity = $min_quantity;
		++$halves;
	}
	
	return \%buckets;
}

sub bucket_sort3 {
	 my $chunks_arr = shift;
	 my $initial_resource = shift;
	 my %buckets = ();
	 
	 my $total_buckets = 100;
	 my $each_bucket = $initial_resource / $total_buckets;
	 my $bucket = 0;
	 for($bucket = 0; $bucket < $total_buckets; ++$bucket) {
	 
	 	my $counter;
	 	foreach my $chunk (@{$chunks_arr}) {
	 		if($chunk > ($bucket * $each_bucket) && $chunk <= (($bucket+1) * $each_bucket)) {
				++$counter;
			}
		}
		
		$buckets{$bucket} = $counter;
	}
	
	return \%buckets;
}