Computing absolutely normal numbers in nearly linear time

A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2021-12, Vol.281, p.104746, Article 104746
Main Authors: Lutz, Jack H., Mayordomo, Elvira
Format: Article
Language:English
Subjects:
Algorithms
Computational complexity
Lempel-Ziv parsing
Martingales
Normal numbers
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c289t-9cdf268d960f87597147bc2f827075ba55e39a049eb18e76d3f2a941c26826863
container_end_page
container_issue
container_start_page 104746
container_title Information and computation
container_volume 281
creator Lutz, Jack H.
Mayordomo, Elvira
description A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.
doi_str_mv 10.1016/j.ic.2021.104746
format article
fullrecord <record><control><sourceid>elsevier_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1016_j_ic_2021_104746</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0890540121000614</els_id><sourcerecordid>S0890540121000614</sourcerecordid><originalsourceid>FETCH-LOGICAL-c289t-9cdf268d960f87597147bc2f827075ba55e39a049eb18e76d3f2a941c26826863</originalsourceid><addsrcrecordid>eNp1j01LxDAQhoMouK7ePfYPdJ3J5qPxJotfsOBFzyFNp5LSjyXpCvvvzVKvwsC8w_AM8zB2j7BBQPXQbYLfcOCYR6GFumArBAMlVxIv2QqqnKUAvGY3KXUAiFKoFTO7aTgc5zB-F65OU3-cqT8V4xQH1xfjcagppiKMxUgu5kUfzqGYw0C37Kp1faK7v75mXy_Pn7u3cv_x-r572peeV2YujW9arqrGKGgrLY1GoWvP24pr0LJ2UtLWOBCGaqxIq2bbcmcE-gzlUts1g-Wuj1NKkVp7iGFw8WQR7FnddjZ4e1a3i3pGHheE8l8_gaJNPtDoqQmR_GybKfwP_wJy9V-T</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Computing absolutely normal numbers in nearly linear time</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Lutz, Jack H. ; Mayordomo, Elvira</creator><creatorcontrib>Lutz, Jack H. ; Mayordomo, Elvira</creatorcontrib><description>A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.</description><identifier>ISSN: 0890-5401</identifier><identifier>EISSN: 1090-2651</identifier><identifier>DOI: 10.1016/j.ic.2021.104746</identifier><language>eng</language><publisher>Elsevier Inc</publisher><subject>Algorithms ; Computational complexity ; Lempel-Ziv parsing ; Martingales ; Normal numbers</subject><ispartof>Information and computation, 2021-12, Vol.281, p.104746, Article 104746</ispartof><rights>2021 The Author(s)</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c289t-9cdf268d960f87597147bc2f827075ba55e39a049eb18e76d3f2a941c26826863</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27923,27924</link.rule.ids></links><search><creatorcontrib>Lutz, Jack H.</creatorcontrib><creatorcontrib>Mayordomo, Elvira</creatorcontrib><title>Computing absolutely normal numbers in nearly linear time</title><title>Information and computation</title><description>A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.</description><subject>Algorithms</subject><subject>Computational complexity</subject><subject>Lempel-Ziv parsing</subject><subject>Martingales</subject><subject>Normal numbers</subject><issn>0890-5401</issn><issn>1090-2651</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp1j01LxDAQhoMouK7ePfYPdJ3J5qPxJotfsOBFzyFNp5LSjyXpCvvvzVKvwsC8w_AM8zB2j7BBQPXQbYLfcOCYR6GFumArBAMlVxIv2QqqnKUAvGY3KXUAiFKoFTO7aTgc5zB-F65OU3-cqT8V4xQH1xfjcagppiKMxUgu5kUfzqGYw0C37Kp1faK7v75mXy_Pn7u3cv_x-r572peeV2YujW9arqrGKGgrLY1GoWvP24pr0LJ2UtLWOBCGaqxIq2bbcmcE-gzlUts1g-Wuj1NKkVp7iGFw8WQR7FnddjZ4e1a3i3pGHheE8l8_gaJNPtDoqQmR_GybKfwP_wJy9V-T</recordid><startdate>202112</startdate><enddate>202112</enddate><creator>Lutz, Jack H.</creator><creator>Mayordomo, Elvira</creator><general>Elsevier Inc</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>202112</creationdate><title>Computing absolutely normal numbers in nearly linear time</title><author>Lutz, Jack H. ; Mayordomo, Elvira</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c289t-9cdf268d960f87597147bc2f827075ba55e39a049eb18e76d3f2a941c26826863</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Algorithms</topic><topic>Computational complexity</topic><topic>Lempel-Ziv parsing</topic><topic>Martingales</topic><topic>Normal numbers</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lutz, Jack H.</creatorcontrib><creatorcontrib>Mayordomo, Elvira</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><jtitle>Information and computation</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lutz, Jack H.</au><au>Mayordomo, Elvira</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Computing absolutely normal numbers in nearly linear time</atitle><jtitle>Information and computation</jtitle><date>2021-12</date><risdate>2021</risdate><volume>281</volume><spage>104746</spage><pages>104746-</pages><artnum>104746</artnum><issn>0890-5401</issn><eissn>1090-2651</eissn><abstract>A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.</abstract><pub>Elsevier Inc</pub><doi>10.1016/j.ic.2021.104746</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0890-5401
ispartof Information and computation, 2021-12, Vol.281, p.104746, Article 104746
issn 0890-5401
1090-2651
language eng
recordid cdi_crossref_primary_10_1016_j_ic_2021_104746
source ScienceDirect Freedom Collection 2022-2024
subjects Algorithms
Computational complexity
Lempel-Ziv parsing
Martingales
Normal numbers
title Computing absolutely normal numbers in nearly linear time
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T07%3A04%3A25IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Computing%20absolutely%20normal%20numbers%20in%20nearly%20linear%20time&rft.jtitle=Information%20and%20computation&rft.au=Lutz,%20Jack%20H.&rft.date=2021-12&rft.volume=281&rft.spage=104746&rft.pages=104746-&rft.artnum=104746&rft.issn=0890-5401&rft.eissn=1090-2651&rft_id=info:doi/10.1016/j.ic.2021.104746&rft_dat=%3Celsevier_cross%3ES0890540121000614%3C/elsevier_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c289t-9cdf268d960f87597147bc2f827075ba55e39a049eb18e76d3f2a941c26826863%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true