My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
December 9th, 2013, 04:38 PM   #1
Senior Member
Joined: Jan 2013

Posts: 209
Thanks: 3

Challenge to computing theory - log but never random access

There is no such thing as random access ever.

Hashtables are said to be near (maybe log of log) random access, going directly to what you look up by a key. Arrays are said to be exactly random access. You give it a memory address and it goes straight there.

But there is a log cost conveniently not counted: the log number of wires in the address bus on the motherboard.

Regardless of if its done in hardware or software, it is a log cost. You pay for maybe 64 wires which do a binary search into the memory. The more memory your data structures are spread across, the more hardware wires or time steps in using the same wire are unavoidable to access them. Its a log cost, not random access.
BenFRayfield is offline  
December 10th, 2013, 01:30 PM   #2
Global Moderator
Joined: May 2007

Posts: 6,275
Thanks: 516

Re: Challenge to computing theory - log but never random acc

Random access means the time to look up is independent of the address, not that there is no cost.
mathman is offline  

  My Math Forum > Science Forums > Computer Science

access, challenge, computing, log, random, theory

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Challenge to the theory of Scalar Fields and Heat Death BenFRayfield Real Analysis 1 March 19th, 2014 04:45 AM
A mathematically perfect democracy and challenge to a theory BenFRayfield Applied Math 6 August 23rd, 2013 04:01 PM
basic random graph theory: xaosman Applied Math 3 November 21st, 2012 07:58 AM
Theory of Computing - DFAs geliot Computer Science 2 February 26th, 2012 09:24 AM
Theory of Computing - DFAs geliot Applied Math 1 December 31st, 1969 04:00 PM

Copyright © 2017 My Math Forum. All rights reserved.