nthdigit/efficient.pl at master · dblando/nthdigit · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#!/usr/bin/perl -w
use strict;
use POSIX;

=pod
Assignment from Kibo:

"Given the infinitely large integer

B = 12345678910111213...

We are only ever interested in finding the Nth digit of B (where N can be anything up to one million.)

Do these four exercises in this order:

1.)  Using only pencil and paper, determine the 500,000th digit of B.

2.)  Write a Perl program that will print the Nth digit of B after actually constructing the entire left half of B (use strings, don't try to use BigNum.)

3.)  Write a Perl program that will print the Nth digit of B without actually constructing the entire left half of B (use the same algorithm you used in problem 1.)

4.)  What is the time complexity of the two programs relative to N? In the same notation, what is their memory usage?"

This program is item 3 in the list.

=cut

use constant max => 1_000_000;

my $usernum;
print "Gimme a whole number between one and a million please\: ";
chomp ($usernum = <>);

if ( $usernum > max )
	{
	$usernum = max;
	print "The number you provided is larger than one million.\n";
	print "Thus I have rolled the number down to one million.\n";
	}

# This section is just some grammatical geekery.
my $ordsuffix;
if ( substr ($usernum, -2, 1) == 1) # numbers ending in 10 through 19
	{
	$ordsuffix = "th";
	}
elsif ( substr ($usernum, -1, 1) == 1)
	{
	$ordsuffix = "st";
	}
elsif ( substr ($usernum, -1, 1) == 2)
	{
	$ordsuffix = "nd";
	}
elsif ( substr ($usernum, -1, 1) == 3)
	{
	$ordsuffix = "rd";
	}
else
	{
	$ordsuffix = "th";
	}


my ($digsize, $turnpoint) = &pivotpoint ($usernum);
print "The calculated number will have $digsize digits and will start at place $turnpoint.\n";
my $localpos = $usernum - $turnpoint;

my $integer  = floor ( $localpos / ($digsize));
my $position = $localpos % ($digsize);

# print "The integer resulting from $localpos is ", $integer + (10 ** ($digsize - 1)) - 1, " with a remainder of $position.\n";

my $componum = ($integer - 1) + (10 ** ($digsize - 1));
my $answer   = substr ($componum, ($position - 1), 1);

print "The integer resulting from $localpos is $componum with a remainder of $position.\n";

print "The $usernum", $ordsuffix," digit has a value of ", $answer, ".\n";

=pod

I now get a different problem:
	7 and 8 get valid answers and number of digits;
	9 gets a valid answer, but the wrong # of digits (2 instead of 1);
	10 gets a valid # of digits but the wrong answer (9 instead of 0);
	11 gets both a valid answer and the correct number of digits.

I get the same edge-case errors around 189, the next increment of digits.
This suggests the error is in &pivotpoint.

Changing "$pivotnum > $placenum" to "$pivotnum >= $placenum" fixed the problem for 9 but not 10.

=cut

sub pivotpoint ()
	{
	my $placenum = shift ;
	my $pivotnum = 0;
	my $oldpivot;
	my $digits = 1;

	until ( $pivotnum >= $placenum )
		{
		my $digsubtotal = 0;
		$oldpivot = $pivotnum;
		$digsubtotal = $digits * ((10 ** $digits) - (10 ** ($digits - 1)));
		$pivotnum += $digsubtotal;
		$digits++;
		}
	$digits--;
	return ($digits, $oldpivot);
	}