DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
nbsystem.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.nbsystem Systèmes de numération
4 # !!! Work in progress !!!
5 
6 ##\file
7 # Systèmes de numération
8 # !!! Work in progress !!!
9 
10 # (c) Olivier Pirson --- DragonSoft
11 # http://www.opimedia.be/DS/
12 # Débuté le 2 août 2006
13 ####################################
14 from __future__ import print_function
15 
16 ## Date du dernier changement pour ce module
17 VERSION = 'nbsystem --- 2010 March 16'
18 
19 import DSPython
20 import DSPython.natural as natural
21 
22 
23 
24 # ###########
25 # Fonctions #
26 #############
27 ## Renvoie le chiffre correspondant au caractère c
28 def chr_to_fig(c):
29  """Renvoie le chiffre correspondant au caractère c
30 
31  Pre: c: caractère alphanumérique
32 
33  Result: naturel <= 36
34 
35  O(1) = ..."""
36  assert isinstance(c, str), type(c)
37  assert c.isalnum(), (type(c), c)
38 
39  return (ord(c) - ord('0') if c.isdigit()
40  else ord(c.upper()) + 10 - ord('A'))
41 
42 
43 ## Naturel correspondant à la représentation de n dans le système de numération de Fibonacci
44 def fibonacci(n):
45  """Renvoie le naturel représentant n (en binaire)
46  dans le système de numération de Fibonacci
47  k k
48  C.-à-d. si n = Sum(b_i * F_(i+2)) alors renvoie Sum(b_i * 2**i)
49  i=0 i=0
50  où b_i = 0 ou 1 tel que si b_i = 1 alors b_(i+1) = 0
51  F_(i+2) = (i+2)ème nombre de Fibonacci
52 
53  Pre: n: naturel
54 
55  Result: naturel "normalisé"
56  suivant le système de numération de Fibonacci
57 
58  O(n) = ..."""
59  assert DSPython.natural_is(n), n
60 
61  if n > 2:
62  # Cherche un i tel que n <= F_(i+2)
63  i = natural.lg(n)
64  (fi_1, fi_2) = natural.fibonacci2(i + 2) # (F_(i+1), F_(i+2))
65  while n > fi_2:
66  i += 1
67  (fi_1, fi_2) = (fi_2, fi_2 + fi_1)
68 
69  # Calcul f par algorithme glouton
70  f = 0
71  while n > 0:
72  while fi_2 > n:
73  i -= 1
74  (fi_1, fi_2) = (fi_2 - fi_1, fi_1)
75  n -= fi_2
76  f = natural.bitset1(f, i)
77  # Le suivant ne peut convenir car pas deux '1' consécutifs
78  i -= 1
79  (fi_1, fi_2) = (fi_2 - fi_1, fi_1)
80  return f
81  else:
82  return n
83 
84 
85 ## Naturel égal à la valeur de f exprimée dans le système de numération de Fibonacci
86 def fibonacci_to_n(f):
87  """Renvoie le naturel égal
88  à la valeur de f exprimée dans le système de numération de Fibonacci
89  k k
90  C.-à-d. si f = Sum(b_i * 2**i) alors renvoie Sum(b_i * F_(i+2))
91  i=0 i=0
92  où b_i = 0 ou 1
93  F_(i+2) = (i+2)ème nombre de Fibonacci
94 
95  Pre: f: naturel ("normalisé" ou non)
96 
97  Result: naturel
98 
99  O(f) = ..."""
100  assert DSPython.natural_is(f), f
101 
102  if f > 2:
103  n = 0
104  from_i = natural.scan1(f)
105  (fi_1, fi_2) = natural.fibonacci2(from_i + 2) # (F_(i+1), F_(i+2))
106  for i in range(from_i, natural.rscan1(f) + 1):
107  if natural.bit(f, i): # chiffre '1'
108  n += fi_2
109  (fi_1, fi_2) = (fi_2, fi_2 + fi_1)
110  i += 1
111  return n
112  else:
113  return f
114 
115 
116 ## "Normalise" f
117 def fibonacci_to_normal(f):
118  """Renvoie n "normalisé" suivant le système de numération de Fibonacci,
119  c.-à-d. renvoie le naturel représentant le même nombre que f
120  dans le système de numération de Fibonacci
121  mais ne contenant pas deux chiffres '1' consécutifs
122 
123  Pre: f: naturel
124 
125  Result: naturel "normalisé"
126  suivant le système de numération de Fibonacci
127 
128  O(f) = ..."""
129  assert DSPython.natural_is(f), f
130 
131  if f > 2:
132  k = natural.rscan1(f) - 1
133  mask111 = 7 << k
134  mask11 = 3 << k
135  mask1100 = mask11 << 2
136  k = 0
137  # Parcours f de la gauche vers la droite
138  while True:
139  while f&mask11 != mask11: # avance tant que pas deux chiffres '1' consécutifs
140  k += 1
141  mask11 >>= 1
142  if mask11 <= 1: # parcours terminé
143  return f
144  mask1100 >>= k
145  mask111 >>= k
146 
147  f ^= mask111 # remplace '011' par '100'
148  if f&mask1100 == mask1100: # faut reculer car formé '1100'
149  k = 0
150  mask11 = mask1100
151  mask1100 <<= 2
152  mask111 <<= 2
153  else: # avancer
154  k = 2
155  mask11 >>= 2
156  else:
157  return f
158 
159 
160 ## ième chiffre de n en base b
161 def fig(n, i, b=2):
162  """Renvoie le ième chiffre de n en base b
163 
164  Pre: n: naturel
165  i: naturel
166  b: naturel >= 2
167 
168  Result: naturel < b
169 
170  O(n, i, b) = ..."""
171  assert DSPython.natural_is(n), n
172  assert DSPython.natural_is(i), i
173  assert DSPython.natural_is(b), b
174  assert b >= 2, b
175 
176  if b == 2: # b == 2
177  return int(natural.bit(n, i))
178  elif natural.nbbits1(b) == 1: # b == 2**k
179  k = natural.scan1(b)
180  return (n >> (k*i)) % b
181  else: # b > 2
182  while (i > 0) and (n > 0):
183  i -= 1
184  n //= b
185  return n%b
186 
187 
188 ## Renvoie le caractère correspondant au chiffre n
189 def fig_to_chr(n, caps=False):
190  """Renvoie le caractère correspondant au chiffre n
191  Si caps alors utlise les lettres majuscules pour représenter les chiffers > 9
192  sinon utlise les lettres minuscules
193 
194  Pre: n: naturel <= 36
195  caps: boolean
196 
197  Result: caractère alphanumérique
198 
199  O(1) = ..."""
200  assert DSPython.natural_is(n), n
201  assert n <= 36, n
202 
203  return (chr(n + ord('0')) if n < 10
204  else chr(n + (ord('A') if caps
205  else ord('a')) - 10))
206 
207 
208 ## Change le ième chiffre de n en base b
209 def figset(n, i, c, b=2):
210  """Renvoie n avec son ième chiffre en base b changé en c
211 
212  Pre: n: naturel
213  i: naturel
214  c: naturel < 2
215  b: naturel >= 2
216 
217  Result: naturel
218 
219  O(n, i, c, b) = ..."""
220  assert DSPython.natural_is(n), n
221  assert DSPython.natural_is(i), i
222  assert DSPython.natural_is(c), c
223  assert c < b, (c, b)
224  assert DSPython.natural_is(b), b
225  assert b >= 2, b
226 
227  if b == 2: # b == 2
228  return natural.bitset(n, i, c)
229  else: # b > 2
230  p = b**i
231  (q, r) = divmod(n, p) # "reste" : chiffres qui précèdent
232  q //= b # "quotient" : chiffres qui suivent
233  return q*(p*b) + (c*p + r)
234 
235 
236 ## Renvoie le naturel correspondant à la liste s de chiffres en base b
237 def list_to(s, b=2):
238  """Renvoie le naturel correspondant à la liste s de chiffres en base b
239  (Si n == [] alors renvoie 0)
240 
241  Pre: s: liste de naturels
242  b: naturel >= 2
243 
244  Result: naturel
245 
246  O(n, b) = ..."""
247  assert DSPython.natural_is(b), b
248  assert b >= 2, b
249 
250  n = 0
251  if b == 2:
252  for i in range(len(s)):
253  assert DSPython.natural_is(s[i]), s[i]
254 
255  n = natural.bitset(n, i, s[i])
256  else:
257  p = 1
258  for c in s:
259  assert DSPython.natural_is(c), c
260 
261  n += p*c
262  p *= b
263  return n
264 
265 
266 ## Renvoie le naturel représenté par s en base b
267 def str_to(s, b=2):
268  """Renvoie le naturel représenté par s en base b
269  (Si n == 0 alors renvoie '0')
270 
271  Pre: s: string ne contenant que des chiffres < b
272  b: 2 <= naturel <= 36
273 
274  Result: naturel
275 
276  O(s, b) = ..."""
277  assert isinstance(s, str), type(s)
278  assert DSPython.natural_is(b), b
279  assert 2 <= b <= 36, b
280 
281  n = 0
282  if b == 2:
283  for i in range(len(s)):
284  assert s[-i-1].isalnum(), (type(s[-i-1]), s[-i-1])
285 
286  n = natural.bitset(n, i, s[-i-1] != '0')
287  else:
288  p = 1
289  for i in range(len(s)):
290  assert s[-i-1].isalnum(), (type(s[-i-1]), s[-i-1])
291 
292  n += p*chr_to_fig(s[-i-1])
293  p *= b
294  return n
295 
296 
297 ## Somme des chiffres de n en base b
298 def sum_figs(n, b=2):
299  """Renvoie la somme des chiffres de n représenté en base b
300 
301  Pre: n: naturel
302  b: naturel >= 2
303 
304  Result: naturel
305 
306  O(n, b) = ..."""
307  assert DSPython.natural_is(n), n
308  assert DSPython.natural_is(b), b
309  assert b >= 2, b
310 
311  if b == 2: # b == 2
312  return natural.nbbits1(n)
313  elif natural.nbbits1(b) == 1: # b == 2**k
314  k = natural.scan1(b)
315  m_k = natural.mersenne(k)
316  s = 0
317  while n > 0:
318  s += n & m_k
319  n >>= k
320  return s
321  else: # autre b
322  s = 0
323  while n > 0:
324  (n, r) = divmod(n, b)
325  s += r
326  return s
327 
328 
329 ## Somme des chiffres alternée de n en base b
330 def sum_figs_alt(n, b=2):
331  """Renvoie la somme des chiffres alterné de n représenté en base b
332  (1er chiffre en positif, 2e en négatif, 3e en positif ...)
333 
334  Pre: n: naturel
335  b: naturel >= 2
336 
337  Result: naturel
338 
339  O(n, b) = ..."""
340  assert DSPython.natural_is(n), n
341  assert DSPython.natural_is(b), b
342  assert b >= 2, b
343 
344  s = 0
345  while n > 0:
346  (n, r) = divmod(n, b)
347  s += r
348  (n, r) = divmod(n, b)
349  s -= r
350  return s
351 
352 
353 ## Renvoie la liste des chiffres de n écrit en base b
354 def to_list(n, b=2):
355  """Renvoie la liste des chiffres de n écrit en base b
356  (Si n == 0 alors renvoie [])
357 
358  Pre: n: naturel
359  b: naturel >= 2
360 
361  Result: liste de naturels (dont le dernier élémént est non nul)
362 
363  O(n, b) = ..."""
364  assert DSPython.natural_is(n), n
365  assert DSPython.natural_is(b), b
366  assert b >= 2, b
367 
368  l = []
369  if b == 2:
370  while n > 0:
371  l.append(n & 1)
372  n >>= 1
373  else:
374  while n > 0:
375  (n, r) = divmod(n, b)
376  l.append(r)
377  return l
378 
379 
380 ## n écrit en base b dans un string
381 def to_str(n, b=2, caps=False):
382  """Renvoie un string représentant n en base b
383  (Si n == 0 alors renvoie '0')
384  Si caps alors utlise les lettres majuscules pour représenter les chiffers > 9
385  sinon utlise les lettres minuscules
386 
387  Pre: n: naturel
388  b: 2 <= naturel <= 36
389  caps: boolean
390 
391  Result: string (dont le premier caractère est différent de '0')
392 
393  O(n, b) = ..."""
394  assert DSPython.natural_is(n), n
395  assert DSPython.natural_is(b), b
396  assert 2 <= b <= 36, b
397 
398  if n > 0:
399  if b == 2:
400  return natural.bin(n)
401  else:
402  l = []
403  while n > 0:
404  (n, r) = divmod(n, b)
405  l.insert(0, fig_to_chr(r, caps=caps))
406  return ''.join(l)
407  else:
408  return '0'
409 
410 
411 
412 # ######\cond MAINTEST
413 # Main #
414 ########
415 if __name__ == '__main__':
416  def main_test():
417  """Test du module"""
418  import sys
419 
420  try:
421  if not 'profile' in dir():
422  import psyco
423  psyco.full()
424  except ImportError:
425  pass
426 
427  import DSPython.debug as debug
428  import DSPython.bit32 as bit32
429  import DSPython.nat32 as nat32
430 
431  debug.test_begin(VERSION, __debug__)
432 
433  print('chr_to_fig()...', end=''); sys.stdout.flush()
434  assert chr_to_fig('0') == 0, chr_to_fig('0')
435  assert chr_to_fig('1') == 1, chr_to_fig('1')
436  assert chr_to_fig('2') == 2, chr_to_fig('2')
437  assert chr_to_fig('9') == 9, chr_to_fig('9')
438  assert chr_to_fig('a') == 10, chr_to_fig('a')
439  assert chr_to_fig('A') == 10, chr_to_fig('A')
440  assert chr_to_fig('z') == 35, chr_to_fig('z')
441  assert chr_to_fig('Z') == 35, chr_to_fig('Z')
442  print('ok'); sys.stdout.flush()
443 
444 
445  print('fibonacci()...', end=''); sys.stdout.flush()
446  assert fibonacci(0) == 0, (fibonacci(0), bit32.bin(fibonacci(0)))
447  assert fibonacci(1) == 1, (fibonacci(1), bit32.bin(fibonacci(1)))
448  assert fibonacci(2) == 2, (fibonacci(2), bit32.bin(fibonacci(2)))
449  assert fibonacci(3) == 4, (fibonacci(3), bit32.bin(fibonacci(3)))
450  assert fibonacci(4) == 5, (fibonacci(4), bit32.bin(fibonacci(4)))
451  assert fibonacci(5) == 8, (fibonacci(5), bit32.bin(fibonacci(5)))
452  for n in range(10000):
453  f = fibonacci(n)
454  assert bit32.bin(f).find('11') == -1, (n, f, bit32.bin(f))
455  s = 0
456  for i in range(bit32.nbbits(f)):
457  if bit32.bit(f, i):
458  s += nat32.fibonacci(i + 2)
459  assert s == n, (n, s, f, bit32.bin(f))
460  print('???', end='')
461  print('ok'); sys.stdout.flush()
462 
463 
464  print('fibonacci_to_n()...', end=''); sys.stdout.flush()
465  assert fibonacci_to_n(0) == 0, (fibonacci_to_n(0), bit32.bin(fibonacci_to_n(0)))
466  assert fibonacci_to_n(1) == 1, (fibonacci_to_n(1), bit32.bin(fibonacci_to_n(1)))
467  assert fibonacci_to_n(2) == 2, (fibonacci_to_n(2), bit32.bin(fibonacci_to_n(2)))
468  assert fibonacci_to_n(3) == 3, (fibonacci_to_n(3), bit32.bin(fibonacci_to_n(3)))
469  assert fibonacci_to_n(4) == 3, (fibonacci_to_n(4), bit32.bin(fibonacci_to_n(4)))
470  assert fibonacci_to_n(5) == 4, (fibonacci_to_n(5), bit32.bin(fibonacci_to_n(5)))
471  for k in range(500):
472  assert fibonacci_to_n(1<<k) == natural.fibonacci(k + 2), \
473  (k, fibonacci_to_n(1<<k), natural.fibonacci(k + 2))
474  assert fibonacci_to_n((1<<k) + 1) == natural.fibonacci(k + 2) + 1, \
475  (k, fibonacci_to_n((1<<k) + 1), natural.fibonacci(k + 2) + 1)
476  assert fibonacci_to_n((1<<k) + (1<<(k+1))) == natural.fibonacci(k + 4), \
477  (k, fibonacci_to_n((1<<k) + (1<<(k+1))), natural.fibonacci(k + 4))
478  assert fibonacci_to_n((1<<k) + (1<<(k+2))) \
479  == natural.fibonacci(k + 2) + natural.fibonacci(k + 4), \
480  (k, fibonacci_to_n((1<<k) + (1<<(k+2))),
481  natural.fibonacci(k + 2) + natural.fibonacci(k + 4))
482  for n in range(10000):
483  f = fibonacci(n)
484  assert fibonacci_to_n(f) == n, (f, fibonacci_to_n(f), n,
485  bit32.bin(fibonacci_to_n(f)), bit32.bin(n))
486  print('???', end='')
487  print('ok'); sys.stdout.flush()
488 
489 
490  print('fibonacci_to_normal()...', end=''); sys.stdout.flush()
491  assert fibonacci_to_normal(0) == 0, \
492  (bit32.bin(0), fibonacci_to_normal(0), bit32.bin(fibonacci_to_normal(0)))
493  assert fibonacci_to_normal(1) == 1, \
494  (bit32.bin(1), fibonacci_to_normal(1), bit32.bin(fibonacci_to_normal(1)))
495  assert fibonacci_to_normal(2) == 2, \
496  (bit32.bin(2), fibonacci_to_normal(2), bit32.bin(fibonacci_to_normal(2)))
497  assert fibonacci_to_normal(3) == 4, \
498  (bit32.bin(3), fibonacci_to_normal(3), bit32.bin(fibonacci_to_normal(3)))
499  assert fibonacci_to_normal(4) == 4, \
500  (bit32.bin(4), fibonacci_to_normal(4), bit32.bin(fibonacci_to_normal(4)))
501  assert fibonacci_to_normal(5) == 5, \
502  (bit32.bin(5), fibonacci_to_normal(5), bit32.bin(fibonacci_to_normal(5)))
503  for n in range(10000):
504  f = fibonacci_to_normal(n)
505  assert bit32.bin(f).find('11') == -1, (n, bit32.bin(n), bit32.bin(f), f)
506  assert f == fibonacci(fibonacci_to_n(n)), (n, f, fibonacci(fibonacci_to_n(n)))
507  assert fibonacci_to_n(n) == fibonacci_to_n(f), (n, fibonacci_to_n(n), fibonacci_to_n(f))
508  print('???', end='')
509  print('ok'); sys.stdout.flush()
510 
511 
512  print('fig()...', end=''); sys.stdout.flush()
513  for n in range(500):
514  for b in range(2, 20):
515  assert fig(n, 0, b) == n%b, (n, b, fig(n, 0, b), n%b)
516  for k in range(10):
517  assert fig(n, k, b) == (n//(b**k))%b, (n, b, k, fig(n, k, b), (n//(b**k))%b)
518  print('ok'); sys.stdout.flush()
519 
520 
521  print('fig_to_chr()...', end=''); sys.stdout.flush()
522  assert fig_to_chr(0) == '0', fig_to_chr(0)
523  assert fig_to_chr(1) == '1', fig_to_chr(1)
524  assert fig_to_chr(2) == '2', fig_to_chr(2)
525  assert fig_to_chr(9) == '9', fig_to_chr(9)
526  assert fig_to_chr(10) == 'a', fig_to_chr(10)
527  assert fig_to_chr(10, caps=True) == 'A', fig_to_chr(10, caps=True)
528  assert fig_to_chr(35) == 'z', fig_to_chr(35)
529  assert fig_to_chr(35, caps=True) == 'Z', fig_to_chr(35, caps=True)
530  print('ok'); sys.stdout.flush()
531 
532 
533  print('figset()...', end=''); sys.stdout.flush()
534  for n in (0, 123):
535  for b in range(2, 40 if debug.assertspeed >= debug.ASSERT_NORMAL else 20):
536  for c in range(b):
537  for k in range(10):
538  new = figset(n, k, c, b)
539  assert fig(new, k, b) == c, (new, b, k, fig(new, k, b), c)
540  for l in range(10):
541  if l != k:
542  assert fig(new, l, b) == fig(n, l, b), \
543  (new, b, k, l, fig(new, l, b), fig(n, l, b))
544  if debug.assertspeed < debug.ASSERT_NORMAL:
545  print(debug.assertspeed_str(), end='')
546  print('ok'); sys.stdout.flush()
547 
548 
549  print('list_to()...', end=''); sys.stdout.flush()
550  assert list_to([0, 0, 1]) == 4, list_to([0, 0, 1])
551  assert list_to((0, 0, 1)) == 4, list_to((0, 0, 1))
552  assert list_to([1, 0, 1]) == 5, list_to([1, 0, 1])
553  assert list_to([2, 1], 3) == 5, list_to([2, 1], 3)
554  assert list_to([5], 10) == 5, list_to([5], 10)
555  assert list_to([14, 1], 16) == 30, list_to([14, 1], 16)
556  for b in range(2, 50):
557  for n in range(1000):
558  s = to_list(n, b)
559  new = list_to(s, b)
560  assert s == to_list(new, b), (b, n, new, s, to_list(new, b))
561  print('???', end='')
562  print('ok'); sys.stdout.flush()
563 
564 
565  print('str_to()...', end=''); sys.stdout.flush()
566  assert str_to('100') == 4, str_to('100')
567  assert str_to('101') == 5, str_to('101')
568  assert str_to('12', 3) == 5, str_to('12', 3)
569  assert str_to('5', 10) == 5, str_to('5', 10)
570  assert str_to('1e', 16) == 30, str_to('1e', 16)
571  for b in range(2, 37):
572  for n in range(1000):
573  s = to_str(n, b)
574  new = str_to(s, b)
575  assert s == to_str(new, b), (b, n, new, s, to_str(new, b))
576  print('???', end='')
577  print('ok'); sys.stdout.flush()
578 
579 
580  print('sum_figs()...', end=''); sys.stdout.flush()
581  for k in range(500):
582  assert sum_figs(2**k - 1) == k, (k, sum_figs(2**k - 1))
583  assert sum_figs(2**k) == 1, (k, sum_figs(2**k))
584  for b in range(2, 50):
585  assert sum_figs(0, b) == 0, (b, sum_figs(0, b))
586  assert sum_figs(1, b) == 1, (b, sum_figs(1, b))
587  for n in range(2**10):
588  assert sum_figs(n, b) == sum_figs(n//b, b) + n%b, \
589  (b, n, sum_figs(n, b), sum_figs(n//b, b))
590  for k in range(50):
591  assert sum_figs(b**k, b) == 1, (b, k, sum_figs(b**k, b))
592  print('???', end='')
593  print('ok'); sys.stdout.flush()
594 
595 
596  print('sum_figs_alt()...', end=''); sys.stdout.flush()
597  for k in range(50):
598  assert sum_figs_alt(2**(2*k) - 1) == 0, (k, sum_figs_alt(2**(2*k) - 1))
599  assert sum_figs_alt(2**(2*k)) == 1, (k, sum_figs_alt(2**(2*k)))
600 
601  assert sum_figs_alt(2**(2*k+1) - 1) == 1, (k, sum_figs_alt(2**(2*k+1) - 1))
602  assert sum_figs_alt(2**(2*k+1)) == -1, (k, sum_figs_alt(2**(2*k+1)))
603  print('???', end='')
604  print('ok'); sys.stdout.flush()
605 
606 
607  print('to_list()...', end=''); sys.stdout.flush()
608  assert to_list(0) == [], to_list(0)
609  assert to_list(4) == [0, 0, 1], to_list(4)
610  assert to_list(5) == [1, 0, 1], to_list(5)
611  assert to_list(5, 3) == [2, 1], to_list(5, 3)
612  assert to_list(5, 10) == [5], to_list(5, 10)
613  assert to_list(30, 16) == [14, 1], to_list(30, 16)
614  for n in range(1, 1000):
615  l = [int(c) for c in natural.bin(n)]
616  l.reverse()
617  assert to_list(n) == l, (n, to_list(n), l)
618  for b in range(2, 50):
619  assert to_list(0, b) == [], (b, to_list(0, b))
620  assert to_list(1, b) == [1], (b, to_list(1, b))
621  for n in range(1, b):
622  assert to_list(n, b) == [n], (b, n, to_list(n, b))
623  for i in range(1, 50):
624  assert to_list(b**i - 1, b) == [b - 1]*i, \
625  (b, i, to_list(b**i - 1, b)) # [b-1,b-1,...,b-1]
626  assert to_list(b**i, b) == [0]*i + [1], \
627  (b, i, to_list(b**i, b)) # [0,0,...,0,1]
628  assert to_list(b**i + 1, b) == [1] + [0]*(i - 1) + [1], \
629  (b, i, to_list(b**i + 1, b)) # [1,0,...,0,1]
630  for n in range(1, 100):
631  assert list_to(to_list(n, b), b) == n, \
632  (b, n, to_list(n, b), list_to(to_list(n, b), b))
633  for n in range(1, 2**40, 10000000000):
634  assert list_to(to_list(n, b), b) == n, \
635  (b, n, to_list(n, b), list_to(to_list(n, b), b))
636  for n in range(2**32 - 100, 2**32 + 100):
637  assert list_to(to_list(n, b), b) == n, \
638  (b, n, to_list(n, b), list_to(to_list(n, b), b))
639  print('ok'); sys.stdout.flush()
640 
641 
642  print('to_str()...', end=''); sys.stdout.flush()
643  assert to_str(0) == '0', to_str(0)
644  assert to_str(4) == '100', to_str(4)
645  assert to_str(5) == '101', to_str(5)
646  assert to_str(5, 3) == '12', to_str(5, 3)
647  assert to_str(5, 10) == '5', to_str(5, 10)
648  assert to_str(30, 16) == '1e', to_str(30, 16)
649  assert to_str(30, 16, caps=True) == '1E', to_str(30, 16, caps=True)
650  for n in range(1000):
651  assert to_str(n) == natural.bin(n), (n, to_str(n), natural.bin(n))
652  for b in range(2, 37):
653  assert to_str(0, b) == '0', (b, to_str(0, b))
654  assert to_str(1, b) == '1', (b, to_str(1, b))
655  for n in range(0, b):
656  assert to_str(n, b) == fig_to_chr(n), (b, n, to_str(n, b), fig_to_chr(n))
657  for i in range(1, 50):
658  assert to_str(b**i - 1, b) == fig_to_chr(b - 1)*i, \
659  (b, i, to_str(b**i - 1, b)) # c...cc
660  assert to_str(b**i, b) == '1' + '0'*i, \
661  (b, i, to_str(b**i, b)) # 10...00
662  assert to_str(b**i + 1, b) == '1' + '0'*(i - 1) + '1', \
663  (b, i, to_str(b**i + 1, b)) # 10...01
664  for n in range(1, 100):
665  assert int(to_str(n, b), b) == n, (b, n, to_str(n, b))
666  if debug.assertspeed >= debug.ASSERT_NORMAL:
667  for n in range(1, 2**40, 10000000000):
668  assert int(to_str(n, b), b) == n, (b, n, to_str(n, b))
669  for n in range(2**32 - 100, 2**32 + 100):
670  assert int(to_str(n, b), b) == n, (b, n, to_str(n, b))
671  if debug.assertspeed < debug.ASSERT_NORMAL:
672  print(debug.assertspeed_str(), end='')
673  print('ok'); sys.stdout.flush()
674  debug.test_end()
675 
676  main_test()
677 ##\endcond MAINTEST