logarithmically spaced integers
I've got here while searching a simple method to get logarithmically spaced series (with base of 10) in python (omitting use of numpy). But your solutions are way to complicated for my ultra simple demands.
def logarithmic_decade(numbers_per_decade, offset=10):
for n in xrange(numbers_per_decade):
yield offset * 10.0 ** (n / float(numbers_per_decade))
Since it's generator in order to getting list you have to:
numbers = list(logarithmic_decade(5))
print numbers
[10.0, 15.848931924611136, 25.118864315095802, 39.81071705534972, 63.095734448019336]
for p, n in zip(numbers, numbers[1:] + [100]):
print 'prev = {p:.2f}, next = {n:.2f}, next/prev = {rt:.4f}'.format(p=p, n=n, rt=n / p)
Gives following the following output:
prev = 10.00, next = 15.85, next/prev = 1.5849
prev = 15.85, next = 25.12, next/prev = 1.5849
prev = 25.12, next = 39.81, next/prev = 1.5849
prev = 39.81, next = 63.10, next/prev = 1.5849
prev = 63.10, next = 100.00, next/prev = 1.5849
The approach in Avaris's answer of generating your log-spaced points directly, is definitely the way to go. But I thought it would be interesting to see how to pick the appropriate value to pass to logspace
to get what you want.
The values in the array generated by logspace(0, k, n)
are the numbers 10ik / (n−1) for 0 ≤ i < n:
>>> numpy.logspace(0, 2, 10)
array([ 1. , 1.66810054, 2.7825594 , 4.64158883,
7.74263683, 12.91549665, 21.5443469 , 35.93813664,
59.94842503, 100. ])
>>> [10 ** (i * 2 / 9.0) for i in xrange(10)]
[1.0, 1.6681005372000588, 2.7825594022071245, 4.641588833612778,
7.742636826811269, 12.91549665014884, 21.544346900318832,
35.938136638046274, 59.94842503189409, 100.0]
This sequence consists of an initial segment where the values are more closely than unit spaced (and so there may be duplicates when they are rounded to the nearest integer), followed by a segment where the values are more widely than unit spaced and there are no duplicates.
>>> ' '.join('{:.2f}'.format(10 ** (i * 2 / 19.0)) for i in xrange(20))
'1.00 1.27 1.62 2.07 2.64 3.36 4.28 5.46 6.95 8.86 11.29 14.38 18.33 23.36
29.76 37.93 48.33 61.58 78.48 100.00'
>>> [int(0.5 + 10 ** (i * 2 / 19.0)) for i in xrange(20)]
[1, 1, 2, 2, 3, 3, 4, 5, 7, 9, 11, 14, 18, 23, 30, 38, 48, 62, 78, 100]
The spacing between values is s(i) = 10iK − 10(i−1)K, where K = k / (n − 1). Let m be the smallest value such that s(m) ≥ 1. (m = 7 in the example above.) Then when duplicates are removed, there are exactly ⌊½ + 10(m−1)K⌋ + n − m remaining numbers.
A bit of algebra finds:
m = ⌈ − log(1 − 10−K) / K log 10 ⌉
Let's check that.
from math import ceil, floor, log
def logspace_size(k, n):
"""
Return the number of distinct integers we'll get if we round
`numpy.logspace(0, k, n)` to the nearest integers and remove
duplicates.
>>> logspace_size(4, 100)
84
>>> logspace_size(4, 121)
100
>>> from numpy import around, logspace
>>> all(logspace_size(k, n) == len(set(around(logspace(0, k, n))))
... for k in xrange(1,10) for n in xrange(2,100))
True
"""
K = float(k) / (n - 1)
m = int(ceil(- log(1 - 10 ** -K) / (K * log(10))))
if m < n:
return int(0.5 + 10 ** ((m - 1) * K)) + n - m
else:
return int(0.5 + 10 ** ((n - 1) * K))
The doctests pass, so this looks good to me. So all you need to do is find n
such that logspace_size(4, n) == 100
. You could do this by binary chop or one of the scipy.optimize
methods:
>>> f = lambda x, k, n:(logspace_size(k, x) - n)**2
>>> int(round(scipy.optimize.fmin(f, 100, args=(4,100), xtol=0.5, ftol=0.5)[0]))
Optimization terminated successfully.
Current function value: 0.015625
Iterations: 8
Function evaluations: 17
122
This is a bit tricky. You can't always get logarithmically spaced numbers. As in your example, first part is rather linear. If you are OK with that, I have a solution. But for the solution, you should understand why you have duplicates.
Logarithmic scale satisfies the condition:
s[n+1]/s[n] = constant
Let's call this constant r
for ratio
. For n
of these numbers between range 1...size
, you'll get:
1, r, r**2, r**3, ..., r**(n-1)=size
So this gives you:
r = size ** (1/(n-1))
In your case, n=100
and size=10000
, r
will be ~1.0974987654930561
, which means, if you start with 1
, your next number will be 1.0974987654930561
which is then rounded to 1
again. Thus your duplicates. This issue is present for small numbers. After a sufficiently large number, multiplying with ratio will result in a different rounded integer.
Keeping this in mind, your best bet is to add consecutive integers up to a certain point so that this multiplication with the ratio is no longer an issue. Then you can continue with the logarithmic scaling. The following function does that:
import numpy as np
def gen_log_space(limit, n):
result = [1]
if n>1: # just a check to avoid ZeroDivisionError
ratio = (float(limit)/result[-1]) ** (1.0/(n-len(result)))
while len(result)<n:
next_value = result[-1]*ratio
if next_value - result[-1] >= 1:
# safe zone. next_value will be a different integer
result.append(next_value)
else:
# problem! same integer. we need to find next_value by artificially incrementing previous value
result.append(result[-1]+1)
# recalculate the ratio so that the remaining values will scale correctly
ratio = (float(limit)/result[-1]) ** (1.0/(n-len(result)))
# round, re-adjust to 0 indexing (i.e. minus 1) and return np.uint64 array
return np.array(list(map(lambda x: round(x)-1, result)), dtype=np.uint64)
Python 3 update: Last line used to be return np.array(map(lambda x: round(x)-1, result), dtype=np.uint64)
in Python 2
Here are some examples using it:
In [157]: x = gen_log_space(10000, 100)
In [158]: x.size
Out[158]: 100
In [159]: len(set(x))
Out[159]: 100
In [160]: y = gen_log_space(2000, 50)
In [161]: y.size
Out[161]: 50
In [162]: len(set(y))
Out[162]: 50
In [163]: y
Out[163]:
array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11,
13, 14, 17, 19, 22, 25, 29, 33, 38, 43, 49,
56, 65, 74, 84, 96, 110, 125, 143, 164, 187, 213,
243, 277, 316, 361, 412, 470, 536, 612, 698, 796, 908,
1035, 1181, 1347, 1537, 1753, 1999], dtype=uint64)
And just to show you how logarithmic the results are, here is a semilog plot of the output for x = gen_log_scale(10000, 100)
(as you can see, left part is not really logarithmic):