Talk:Lookup table

Image processing?[edit]

From the article: In image processing, lookup tables are often called LUTs, and they link index numbers to output values. One common LUT, called the colormap, is used to determine the colors and intensity values with which a particular image will be displayed.

Does the image processing LUT definition have anything to do with traditional lookup tables in computer science? --Abdull 23:07, 3 October 2005 (UTC)[reply]

Table computation time[edit]

I removed this:

The other restriction, may be more important, is the time, required for the preliminary evaluation of the function`s values. For example: if the argument has 64 bits then one should preliminary evaluate 264 = 1,8 * 1019 values of the function. If one value evaluation requires, for example, 1 mcsec (10 − 6sec), then the evaluation of the 1,8 * 1019 values requires appr. 580 000 years!!

The reason is quite simple: any lookup table that takes an extremely long time to compute also takes up an extremely large amount of space. Space is the fundamental limitation. Say you have a 10 terabyte drive filled with a lookup table and each element takes a microsecond to compute. Then the total time is only 16 weeks, which isn't that bad.

That's not to say there aren't applications where the precomputation time is prohibitive, either because the time per element is large or because the table is very large and disk-based. I removed the example and de-emphasized this part. Deco 22:04, 13 February 2006 (UTC)[reply]

"Space is the fundamental limitation."

But time is the fundamental limitation as well. (Vladimir Baykov)

No, it's not. That's exactly what I explained above. Unless each table element is extremely expensive to compute, or there is little time available for precomputation, space will almost always be the limiting factor. Deco 08:45, 15 February 2006 (UTC)[reply]

OK, you are right "space will almost always be the limiting factor" In the frame of technologies - yes! Many people think so. But if you try to think widely you understand, that time limit for DIRECT table lookup method for wordlength 64-128 is very important thing, may be more important, than the space of table.

It is true that, given infinite memory in which to store the table, time may become a limiting factor, but this is a purely hypothetical situation. I get your point though - just not sure whether or not it actually belongs in the article or not. Deco 22:42, 15 February 2006 (UTC)[reply]

You guess, that 64 bit word-length is only PURELY HYPOTHETICAL situation?? Really so? Even in 1985, when I first time noted that, 64 bit word-length was the standard for IBM-360.

Very importatnt restriction of the table lookup method is the time, required for the preliminary evaluation of the function`s values. For example: if the argument has 64 bits then one should preliminary evaluate 2**64 = 1,8 * 10**19 values of the function. If one value evaluation requires, for example, 1 mcsec (10**( - 6)sec), then the evaluation of the 1,8 * 10**19 values requires appr. 580 000 years!! —Preceding unsigned comment added by 77.181.169.204 (talk) 07:53, 16 September 2008 (UTC)[reply]

I am quoting from the "history":

"22:02, 13 February 2006 Deco (Move new content up - remove silly example about 2^64 size table, since there's not enough space anywhere for such a table anyway)"

I guess that in any discussion to say SILLY about the other opinion, as said Deco, can only bad brought up persons. I don`t know whether it is acceppted or not to say so to professors in American universities, but in the European Universities no one professor never say so even to the students or to the postgraduates. I guess this person must apologize.

Vladimir Baykov References

Reverse Lookup table?[edit]

I think that should be noted that the LUT operation can be reversed via hashing, e.g.:

Given:

f(x) = (r,g,b)

Where f(x) is a LUT, and the 'x' argument is a color index, and the result is a RGB555/RGB888 color vector.

Then, a f^-1(r,g,b) = x can be built using a hash table, depending on the color accuracy you need:

RLUT hash table = 2^(bits_of(R)+bits_of(G)+bits_of(B))

And the formula for f^-1(r,g,b), that retrieves the index could be written as (example):

x = HashTable[R<<(bits_of(G)+bits_of(B)) | G<<bits_of(B) | B]

Do you think that would be interesting to add an RLUT article and a reference from this one? --faragon 10:46, 8 May 2007 (UTC)[reply]

Sine plot too large[edit]

The plot of the sampled sine curve is unnecessarily large, and overlaps the text in the paragraphs below (at least on my system, which has a resolution of 1024 x 768, and has the browser maximised). I'd fix this if I knew how to. — Paul G 09:31, 12 October 2007 (UTC)[reply]

Suggest complete re-write of the article[edit]

I think the article has been writen by someone with quite limited knowldge of lookup tables. I believe the examples given are unrepresentative of most real-world lookup tables that are frequently simply associative arrays, either unsorted or sorted.

The article should cover these simple cases first and then cover trivial hash function lookups on one-dimensional tables (these being very beneficial in many situations - and very much under-utilized by programmers) and then go on to cover binary search of sorted tables, then last, but not least, hash functions.

It should also touch on memoization techniques and give examples for several ways that lookup tables can save both significant code repetition, and aid clarity.

As the article stands, a casual or inexperienced user might be put off by the view expressed that "modern processors are better off without lookup tables because tables don't fit in cache". Many lookup tables can actually be shorter than the code required to calculate values afresh, especially if the range is short and the table can be statically defined close to its use to improve locality of reference.ken (talk) 11:14, 14 December 2009 (UTC)[reply]

Done (1st draft)ken (talk) 12:33, 14 December 2009 (UTC)[reply]

External links modified[edit]

Hello fellow Wikipedians,

I have just added archive links to one external link on Lookup table. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

Added archive http://web.archive.org/web/20150912031501/http://webster.cs.ucr.edu/AoA/Windows/HTML/TableLookups.html to http://webster.cs.ucr.edu/AoA/Windows/HTML/TableLookups.html

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 07:45, 28 February 2016 (UTC)[reply]

Sine: 1/8 th of a period is enough[edit]

"symmetry rules. In this case, the lookup table is calculated by using the sine function for the first quadrant (i.e. sin(0..pi/2)). When we need a value, we assign a variable to be the angle wrapped to the first quadrant. We then wrap the angle to the four quadrants (not needed if values are always between 0 and 2*pi) and return the correct value (i.e. first quadrant is a straight return, second quadrant is read from pi/2-x, third and fourth are negatives of the first and second respectively). For cosine, we only have to return the angle shifted by pi/2"
Using the cumulative sum or differences between values is enough to reconstruct all values from just 1/8-th. Due to the differential or integral relation between sine and cosine one might just store 0 to pi/4 and generate the rest from those values. Example: $10*(\sin(15/32\cdot \pi )-\sin(13/32\cdot \pi ))/2\approx \sin(2/32\cdot \pi )$ --Moritzgedig (talk) 19:34, 3 April 2021 (UTC)[reply]

Layman intro please[edit]

Please can someone adjust the start (at least) of the introduction to explain the topic in non-technical terms? Onanoff (talk) 08:48, 27 July 2022 (UTC)[reply]