Row of natural numbers

Question

Definition

There is infinite row of concatenated natural numbers (positive integers, starting with 1):

1234567891011121314151617181920212223...

Challenge

• Write program in any language, that accepts position number as an input, and outputs digit from that position in the row defined above.
• Position number is arbitrary size positive integer. That is first position is 1, yielding output digit '1'
• Input is either in decimal (eg. 13498573249827349823740000191), or e-notation (eg. 1.2e789) corresponding to positive integer.
• Program has to end in reasonable time (10 seconds on modern PC/Mac), given very large index as an input (eg. 1e123456 - that is 1 with 123456 zeroes). So, simple iteration loop is not acceptable.
• Program has to terminate with an error in 1 s, if given any invalid input. Eg. 1.23e (invalid), or 1.23e1 (equals to 12.3 - not an integer)
• It's ok to use public BigNum library to parse/store numbers and do simple mathematical operations on them (+-*/ exp). No byte-penalty applied.
• Shortest code wins.

TL;DR

• Input: bignum integer
• Output: digit at that position in infinite row 123456789101112131415...

Some acceptance test cases

in notation "Input: Output". All of them should pass.

• 1: 1
• 999: 9
• 10000000: 7
• 1e7: 7 (same as row above)
• 13498573249827349823740000191: 6
• 1.1e10001: 5
• 1e23456: 5
• 1.23456e123456: 4
• 1e1000000: 0
• 1.23e: error (invalid syntax)
• 0: error (out of bounds)
• 1.23e1: error (not an integer)

Bonus!

Output digit position number inside the number, and output number itself. For example:

• 13498573249827349823740000191: 6 24 504062383738461516105596714
  • That's digit '6' at position 24 of number '504062383738461516105596714'
• 1e1000000: 0 61111 1000006111141666819445...933335777790000
  • Digit '0' at position 61111 of 999995-digit long number I'm not going to include here.

If you fulfill the bonus task, multiply size of your code by 0.75

Credit

This task was given at one of devclub.eu gatherings in year 2012, without large number requirement. Hence, most answers submitted were trivial loops.

Have fun!

Answer 1

CJam, 78 bytes

r_A,s-" e . .e"S/\a#[SSS"'./~'e/~i1$,-'e\]s"0]=~~_i:Q\Q=Qg&/
s,:L{;QAL(:L#9L*(*)9/-_1<}g(L)md_)p\AL#+_ps=

The program is 104 bytes long and qualifies for the bonus.

The newline is purely cosmetic. The first line parses the input, the second generates the output.

Try it online!

Idea

For any positive integer k, there are 9×10^k-1 positive integers of exactly k digits (not counting leading zeroes). Thus, if we concatenate all of them, we obtain an integer of 9×n×10^k-1.

Now, concatenating all integers of n or less digits yields an integer of

digits.

For a given input q, we try determine the highest n such that the above expression is smaller than q. We set n := ⌈log₁₀q⌉-1, then n := ⌈log₁₀q⌉-2, etc. until the desired expression becomes smaller than q, subtract the resulting expression from q (yielding r) and save the last value of n in l.

r now specifies the index in the concatenation of all positive integers of l+1 digits, which means that the desired output is the r%(l+1)^th digit of the r/(l+1)^th integer of l+1 digits.

Code (input parsing)

r_          e# Read from STDIN and duplicate.
A,s-        e# Remove all digits.
" e . .e"S/ e# Push ["" "e" "." ".e"].
\a#         e# Compute the index of the non-digit part in this array.

[SSS"'./~'e/~i1$,-'e\]s"0]

            e# Each element corresponds to a form of input parsing:
            e#   0 (only digits): noop
            e#   1 (digits and one 'e'): noop
            e#   2 (digits and one '.'): noop
            e#   3 (digits, one '.' then one 'e'):
            e#     './~    Split at dots and dump the chunks on the stack.
            e#     'e/~    Split the and chunks at e's and dump.
            e#     i       Cast the last chunk (exponent) to integer.
            e#     1$      Copy the chunk between '.' and 'e' (fractional part).
            e#     ,-      Subtract its length from the exponent.
            e#     'e\     Place an 'e' between fractional part and exponent.
            e#     ]s      Collect everything in a string.
            e#   -1 (none of the above): push 0

~           e# For s string, this evaluates. For 0, it pushes -1.
~           e# For s string, this evaluates. For -1, it pushes 0.
            e# Causes a runtime exception for some sorts of invalid input.
_i:Q        e# Push a copy, cast to Long and save in Q.
\Q=         e# Check if Q is numerically equal to the original.
Qg          e# Compute the sign of Q.
&           e# Logical AND. Pushes 1 for valid input, 0 otherwise.
/           e# Divide by Q the resulting Boolean.
            e# Causes an arithmetic exception for invalid input.

Code (output generation)

s,:L     e# Compute the number of digits of Q and save in L.
{        e# Do:
  ;      e#   Discard the integer on the stack.
  Q      e#   Push Q.
  AL(:L# e#   Push 10^(L=-1).
  9L*(   e#   Push 9L-1.
  *)     e#   Multiply and increment.
  9/     e#   Divide by 9.
  -      e#   Subtract from Q.
  _1<    e#   Check if the difference is non-positive.
}g       e# If so, repeat the loop.
(        e# Subtract 1 to account for 1-based indexing.
L)md     e# Push quotient and residue of the division by L+1.
_)p      e# Copy, increment (for 1-based indexing) and print.
\AL#+    e# Add 10^L to the quotient.
_p       e# Print a copy.
s        e# Convert to string.
2$=      e# Retrieve the character that corresponds to the residue.

Answer 2

CJam, 75 * 0.75 = 56.25

This is quite fast, one iteration per digit of the number that contains the desired position. I'm sure it can be golfed a lot more, it's quite crude as it is.

q~_i_@<{0/}&:V9{VT>}{T:U;_X*T+:T;A*X):X;}w;U-(_X(:X/\X%10X(#@+s_2$\=S+@)S+@

Give the position as input, the output is:

<digit> <position> <full number>

Try it online.