Usar tablas de referencia para habilitar la imposibilidad

Vergonzoso confesionario: nunca aprendí las tablas de multiplicar en un gimnasio. Claro, tenía las tablas fáciles como el dos y el cinco, pero si me preguntaras qué es 4 x 7 u 8 x 6, dibujaría blancas. Como puede imaginar, eso me hizo menos un estudiante de matemáticas estrella, y estaba especialmente discapacitado durante las pruebas de tiempo limitado con muchos problemas de multiplicación largos. El algoritmo estándar es mucho más rápido cuando recuerdas esas matrices, como descubrí para mi gran aflicción.

Me acordé de este doloroso recuerdo cuando vi la Supercon 2019 de Charles Lohr hablando sobre la utilidad y flexibilidad de las tablas de búsqueda, o LUT, y su capacidad para facilitar o incluso evitar por completo las operaciones intensivas en computadoras. Por supuesto, la mayoría de las implementaciones de LUT tratan problemas un poco más complejos que las tablas de multiplicar, pero no son necesarios. Como señala Charles, incluso las tablas de senos y logaritmos que antes se llenaban página tras página en los trabajos de referencia se han trasladado al silicio, donde encontrar la respuesta correcta basada en la entrada del usuario es mucho más fácil que obtener la respuesta en una computadora.

Sí, este es un servidor de Minecraft, todo gracias a LUT.

Uno de los ejemplos más interesantes de cómo los LUT pueden lograr lo aparentemente imposible radica en un antiguo proyecto en el que Charles intentó construir un servidor de Minecraft en ATMega168. Enviar bits (las representaciones de datos de una parte del mundo del juego) a los clientes es el trabajo esencial de un servidor de Minecraft, y en máquinas normales, lo que implica el uso de compresión de datos. En lugar de intentar implementar zlib en un microcontrolador de 8 bits, recurrió a LUT, que solo alimenta los bytes sin procesar al cliente, sin que el servidor tenga la menor idea de lo que significa. Algunos inversores potentes utilizan una técnica similar que sintetizan una salida sinusoidal alimentando un ciclo completo de valores a un DAC de una matriz de bytes. Es una fuerza bruta, pero funciona.

Otro hallazgo fascinante e inesperado es que los LUT no necesariamente tienen que ser programas. Algunos se pueden implementar en sistemas completamente mecánicos. Charles usó el ejemplo de levas en un eje; en el motor de un automóvil, estos representan el código necesario para abrir y cerrar las válvulas a tiempo para cada cilindro. Ejemplos más complicados son las levas y los kits que alguna vez se encontraron en las computadoras de escopeta para armas de barcos, o las tarjetas de software utilizadas para los telares Jacquard. Incluso le da la vuelta a la máquina de mármol Wintergatan, con su gran tambor de programa y clavijas que actúan como hardware LUT.

Encontré el discurso de Charles extenso y fascinante. Originalmente pensé que se trataba de conversaciones intensivas en FPGA, pero en realidad no llegó a las cosas específicas de FPGA hasta el final. Sin embargo, eso funcionó bien: solo escuchar todos los problemas de resfriado que puede resolver LUT valió el precio de la entrada.

Y para los curiosos, sí, finalmente memoricé las tablas de multiplicar. Curiosamente, me hizo clic solo después de que comencé a jugar con números y a ver sus relaciones con mi primera calculadora, que, irónicamente, probablemente usó LUT para calcular los resultados.

  • Ostraco dice:

    "Vergonzoso tiempo de confesión: nunca aprendí las tablas de multiplicar en un gimnasio".

    Un escritor muy práctico. 😉

    "Por supuesto, la mayoría de las implementaciones de LUT tratan problemas un poco más complejos que las tablas de multiplicar, pero no es necesario".

    Encuéntrelos en programas de fotos y videos.

  • Sr. Nada dice:

    Una vez necesité senos y cosenos rápidos para números de punto fijo. Terminé haciendo una hoja de cálculo para calcular los números y descartar los datos en eeprom. funcionó perfectamente.

    • Linterna mágica dice:

      Históricamente, en el coprocesador matemático Intel '386, una sola entrada en una tabla de búsqueda erraba y provocaba una revocación.

      • Foobacca dice:

        Solo sabía sobre el error Pentium FDIV. Tendré que mirar eso.

        • rasz_pl dice:

          https://www.verifsudha.com/2017/09/11/pentium-fdiv-bug-curious-engineer/ "La implementación de la tabla de búsqueda SRT de Pentium es una matriz de 2048 celdas. Solo 1066 de estas celdas contenían realmente la valores. Debido a un problema en la carga del script de la tabla de búsqueda, 5/1066 entradas no se programaron con valores válidos. "

    • Elliot Williams dice:

      Mi truco favorito sobre LUT: los antiguos chips de modulación de frecuencia de Yamaha tenían registros LUT de seno y otro LUT para mejorar Todas las piezas (sin) (sin) (y) se hacen como exp (log (sin (x))) + log ( sin (y))), con todas las matemáticas difíciles hechas en LUT. Esto reduce las matemáticas a tres búsquedas y una suma.

      Aquí hay una foto de los LUT, para los escépticos:
      https://docs.google.com/document/d/18IGx18NQY_Q1PJVZ-bHywao9bhsDoAqoIn1rIm42nwo/edit?pli=1

      Esta fue una gran charla sobre un "truco" muy útil para conocer.

      • Daniel Larrosa dice:

        ¡Buen truco! Gracias por la referencia.

        Solo un pequeño detalle: creo que la fórmula debería ser "exp (log (sin (x)) + log (sin (y)))" lo describiste correctamente en el texto: "Eso reduce las matemáticas a tres búsquedas y una suma ”.

        Más amigable,
        A / P Daniel F. Larrosa
        Montevideo, Uruguay

        • Elliot Williams dice:

          Gracias. Arreglado. Sí, es un gran truco.

    • RW versión 0.0.1 dice:

      Meh, solo búscalo 0, 15, 30, 45, 60, 75 y 90 grados y deja que interpole el resto.

      • Un hombre viejo dice:

        No sé grados. Los radianes son mi bolso. ¡Son los más educados! La tasa de cambio del seno (x) cambia constantemente, por lo que se interpola durante un intervalo de 15 grados. No es mi primera opción.

        • Sr. Nada dice:

          i uno como grados binarios donde 256 = 360 = 2pi. por lo tanto, coincide con un solo tipo de datos de 8 bits. muy amigable.

          • Sykobee dice:

            Con un poco de matemáticas de índice de búsqueda (que puede obtener de forma gratuita dependiendo de la implementación de su ROM de búsqueda), solo necesita almacenar una cuarta parte del seno, también la mitad de la onda es más fácil con solo rechazar el resultado. para la segunda mitad de la ola.

      • Daniel Scott Matthews dice:

        Si desea hacer atajos, puede tener una LUT mucho más pequeña (algo ancha), que solo mantiene la diferencia entre una onda sinusoidal y una triangular, porque las partes relevantes de esta última son una pendiente simple. es decir, 16 bits de senos con 8 bits LUT más algunas matemáticas simples. No estoy seguro, pero las LUT con una cadena de vectores serían aún más compactas, y eso se relacionaría con la idea de interpolación.

    • Steven Clark dice:

      Encontré GNU Octave que vale la pena aprender. De esa manera, podría simplemente escribir un script que escupe código fuente preformateado.

    • Stuart Longland dice:

      Solo estoy escribiendo un guión:

      https://github.com/sjlongland/atinysynth/blob/master/gensine.py

      que luego llamo desde el Makefile:

      https://github.com/sjlongland/atinysynth/blob/master/Makefile#L42-L45

  • Beto dice:

    Una vez construí un altímetro que usaba un ADC de 16 bits. Necesitaba traducir la presión de la presión en una relación muy no lineal con la altura.

    Los 8 bits superiores se tradujeron a una tabla de alturas leída por "Piece Simple Interpolation". Los 8 bits inferiores se tradujeron en alturas medias por diferencias proporcionales entre rangos sucesivos de bytes superiores.

    El proceso se describe en la nota de aplicación de Microchip AN942. Sigue siendo útil cuando se utilizan microcontroladores con funciones matemáticas complejas limitadas.

    • RW versión 0.0.1 dice:

      Considérelo, todas las ECU de 8 bits de los 80 y principios de los 90 (OBD-1, EEC-IV, SMEC, etc.) utilizan tablas de búsqueda similares en ROM para la relación aire-combustible, la altitud y la compensación barométrica, cualquier cosa que no sea línea.

      • JohnJ dice:

        Trabajé con el tipo que diseñó el primer EFI para Chrysler. Dijo que usó 1802 y un conjunto simple de tablas de búsqueda para decidir la duración del pulso de inyección. Usó solo un vacío y RPM (¿y la posición del acelerador?) Y aún así golpeó el carburador más complejo.

        • Nick L dice:

          Curiosamente, todas las tablas EFI modernas todavía funcionan con tablas de búsqueda de tiempo de iluminación, combustible, etc. Con algunos recortes a largo plazo agregados (y control de bucle cerrado en algunos escenarios)

      • Bill Stewart dice:

        Estaba trabajando en un proyecto de control del tráfico aéreo a mediados de los 80. Inicialmente nos eligieron porque nuestro chip deslizante se puso en marcha más rápido que casi todo lo demás. Hubo otras razones por las que nosotros (afortunadamente para nosotros, y quizás también para usted) no tuvimos éxito en el proyecto, pero para la parte de diapositivas, descubrimos que los datos del radar provienen de transformadores A / D de 10 bits y 1024 elementos una tabla de búsqueda es realmente MUCHO más rápida que hacer un disparo deslizante.

    • Dibujos dice:

      Todavía estoy pensando en una forma de hacer un altímetro mecánico para ayudar a corregir la mezcla de aire y tornillo en el carburador para poder viajar sin parar en Pikes Peak a toda velocidad en mi viejo BMW a pesar de un cambio en la presión del aire.

      ¿Tiene enlaces a este proyecto? Podría terminar por la vía electrónica

      • Ostraco dice:

        https://www.microchip.com/wwwAppNotes/AppNotes.aspx?appnote=en020511

      • Doug dice:

        Los viejos carburadores Rochester Quadrajet usaban varillas de medición puntiagudas para adaptar la mezcla A / F en condiciones cambiantes. Incluso los motores GM I6 más grandes usaban una versión de calibre generalizado del Quadrajet, esencialmente un Quadrajet dividido por detrás. Tengo mis dudas de que el ajuste de los tornillos del mezclador pueda funcionar tan rápido como las varillas de medición, así que sí, EFI probablemente esté en su futuro Pike's Peak. Diviértete y mantén el rumbo. No es frecuente que se produzca un cambio de cabeza motorizada en HaD.

    • JohnJ dice:

      Yo, con mi jefe en ese momento, hice exactamente lo que fue el primer altímetro electrónico utilizado en un dron de objetivo de misiles para aviones de haya alrededor de 1990.

      Usamos 2 ADC de 24 bits que alternaban entre autocalibración y lectura para compensar la barra de temperatura cuando el dron golpeaba MACH 4 verticalmente y se arqueaba hacia abajo, luciendo exactamente como un SCUD a aproximadamente 100,000 pies. (El dron costó $ 100 mil en lugar del $ 1 millón que pagamos a Rusia por SCUD reales para practicar disparos).

      Esta cosa podría medir con precisión entre el piso y por encima de su cabeza, y llegar a 110,000 pies sin ninguna pérdida de precisión entre -40C y 85C. No recuerdo el precisión nominal, pero ninguna de mis unidades se apagó más de 500 pies por 110.000 pies.

      Las tablas de búsqueda nos permitieron usar los sensores de presión más allá de su precisión estimada y rango de temperatura simplemente caracterizando cada sensor de unidad individual y ADC a 7 temperaturas y una multitud de altitud / presiones. Usamos Excel para convertir los datos en tablas para cada temperatura y presión. Afortunadamente, las galgas extensométricas de sílice son en realidad bastante lineales, excepto en los extremos (más allá de la hoja de datos) de sus escalas.

      Desafortunadamente, han pasado 3 décadas, así que no recuerdo exactamente cómo entrelacé la presión del sensor con la temperatura.

      Los resultados se publicaron en DAC, que le dio al dispositivo una salida lineal de pie a voltaje. Esa característica por sí sola necesitaba una interpolación de línea de piezas (que describí por primera vez en una nota en una aplicación nacional de semiconductores alrededor de 1975) porque no pudimos encontrar una presión en una ecuación de altitud lo suficientemente precisa como para calcularla con un uP de 8 bits (su problema también).

      Comencé a hacer la calibración manualmente, pero luego automaticé el proceso ejecutando el calibrador Pitot y una cámara multimedia con VBA en una celda de la recopilación de datos de Excel.

  • acrónimos innecesarios dice:

    Gracias a Pete, ¿por qué demonios sentiste la necesidad de acortar las tablas de búsqueda a LUT? Es simplemente doloroso y molesto. Deje de escribir sugerencias del Departamento de Defensa.

    en un frente vagamente temático, en los viejos tiempos de la informática, era un lugar común para nosotros buscar matrices para reemplazar los cálculos costosos de la CPU, generalmente funciones de trigo o de grabación, en los motores de juegos. Fue nostálgico verlo usado de nuevo.

    • hex4def6 dice:

      ... ¿Porque ese es un estándar de la industria para ellos? Generalmente, es útil tener etiquetas para las ideas. De esa manera, cuando alguien dice "CPU" o "LUT", la audiencia puede estar bastante segura de qué tipo de espacio problemático está hablando. Compare "int" con "integer;" ¿los consideras iguales? No lo hago, a pesar de que "int" es solo una versión abreviada de "integrador". Tiene un matiz que se le atribuye. Si hablamos de C, eso podría significar que es un número de 16 bits.

      Lo mismo con la tabla LUT vs Lookup. LUT podría tener implicaciones que el término generalizado "tabla de búsqueda" no tiene.

    • Pelrun dice:

      ¡Oye, no comencemos LUT avergonzados aquí!

      • Elliot Williams dice:

        ¡Ja ja! Tuve que leer eso en voz alta.

  • Mate dice:

    Utilizo LUT en un PIC de 8 bits con cuatro GPIO a DAC de hardware (R2R) para generar un seno como parte de un banco de pruebas automatizado. Debido a que funciona con una frecuencia fija, pude diseñar un filtro efectivo para la salida y obtener menos del 0.015% de THD, que es suficiente para la prueba. Una solución de $ 5 para reemplazar el instrumento de $ 4,000 que generalmente especificamos.

    • Comedias dice:

      Echa un vistazo a "Magic Sine Waves" de Don Lancaster.

    • Jon dice:

      Cuando necesitaba invertir los bits de bytes en un microcontrolador, que es más difícil de hacer de lo que parece, utilicé una tabla de búsqueda. De hecho, utilicé una matriz de bytes donde el valor de entrada era el índice y el valor de la matriz era el byte invertido.

    • Elliot Williams dice:

      ¿Dónde traza la línea entre la reproducción de muestra / DDS y "usar LUT para el seno"?

      Pero si. Misma misma.

      • Mate dice:

        Mi LUT sinusoidal es de 126 bytes, y el programa completo (en ensamblado) tiene aproximadamente 45 líneas (141 con todos los comentarios y definiciones). No hará esto mediante la reproducción de ejemplos.

  • Jon dice:

    En la automatización de procesos, utilicé LUT para resolver los principales problemas comerciales, mientras me enfocaba en los requisitos para una verdadera solución comercial. Que es lo contrario de lo que estaba hablando. Creo nueces a partir de la salida de personas realmente inteligentes, luego el cuidado continuo muestra lo que significan las entradas para la salida. Esto luego impulsa el proceso de RFP para garantizar que cuando procesamos el proceso, cumplimos con los requisitos reales sin demasiado. Parece al revés, pero nos permite hacer un trabajo aparentemente aleatorio y transformarlo en interiores deterministas.

    • a_do_z dice:

      Me interesaría leer un estudio de caso o cualquier edición de uno de esos proyectos.

    • mímica dice:

      parece que puede ser útil, pero no entiendo a qué te refieres. Por favor, dé un ejemplo.

    • Jonkangas dice:

      Cuando llegué a mi empleador, teníamos documentos verbales que describían la seguridad estándar en nuestra aplicación principal. Dependiendo del rol del usuario, configuraríamos alrededor de 150 campos.

      Exporté esos 150 campos a todos los usuarios, luego usé la base de datos de recursos humanos para que esos usuarios identificaran roles individuales. Hizo una gran brecha para normalizar la construcción de cada función y poner todo en una gran hoja de cálculo de Excel.

      Hemos construido a partir de esa demografía combinada de usuarios y estamos buscando información sobre el rol de la mesa hasta que podamos limpiar las entradas al único mínimo necesario para la construcción estándar.

      Una vez que tuvimos a los empleados bajo control, usamos el mismo proceso para mapear a todos los demás solicitantes de autoridad. Después de hacer eso, creamos una tabla de búsqueda similar para otros 5 programas.

      Al construir la tabla de búsqueda, nos dimos cuenta de que el mantenimiento continuo era enorme porque los roles identificados eran muy dinámicos, pero la construcción requerida no lo era. También notamos que algunos campos estaban estrechamente vinculados al título del trabajo y algunos estaban vinculados a la ubicación. Por lo tanto, al escribir nuestra RFP tenemos requisitos específicos que necesitaremos para reducir la necesidad de mantenimiento.

      La tabla de búsqueda también nos permitió duplicar nuestra capacidad sin duplicar nuestro personal mientras reuníamos las piezas humanas, escribíamos el proceso alrededor de la tabla de búsqueda y lo automatizamos parcialmente. También lo hicimos reduciendo nuestros tiempos de procesamiento en un 50%.

      El próximo año reorganizaremos el proceso para satisfacer las necesidades comerciales. Esto incluye conceptos básicos como la administración de roles funcionales de grupos, ciclos de vida de roles dinámicos, administración de ciclos de vida excepcionales, administración de derechos, y nos encargaremos de la administración de todos los programas principales de la organización.

      Entonces, entiendo que esto es genial, no hardware, busco tablas en silicona. Pero ... reconocí tanto del discurso en mi propio trabajo que pensé en mencionarlo mientras trabajaba en el proceso empresarial.

  • Dibujos dice:

    Siempre me han fascinado las levas de calculadora de las antiguas armas navales. Me gustaría un artículo sobre cómo se desarrollaron.

    • Ostraco dice:

      Suponga que se refiere a las levas balísticas.

      https://archive.org/stream/B-001-002-575/B-001-002-575_djvu.txt

  • limroh dice:

    "Vergonzoso tiempo de confesión: nunca aprendí las tablas de multiplicar en un gimnasio".

    ¿Por qué es tan vergonzoso? Ni siquiera he oído hablar de las tablas de multiplicar (o nunca las aprendí e inmediatamente las olvidé) en un gimnasio, gimnasio o universidad.

    Lo siguiente no es del todo correcto y algo completo, pero me gustan las matemáticas porque cada problema se puede resolver reduciéndolo a (las) reglas básicas.
    Así que me alegro de no haber tenido nunca la necesidad de memorizar tales matrices de memoria, porque eso es exactamente lo contrario de ese principio.
    La misma razón por la que las matemáticas en la universidad no eran tan "divertidas" porque, por ejemplo, Las integrales "complicadas" con seno, pastel, raíz, etc. no se pueden integrar simplemente de manera tan lógica sin una matriz (memorizada) de las, llamémoslas, integraciones de cable.

    Mi filosofía personal a este respecto es que no quiero "desperdiciar" capacidad simplemente almacenando información cuando solo se puede almacenar en otro lugar (papel, computadora, etc.). Mi énfasis está en poder usar, combinar y procesar dicha información almacenada "externamente".
    Ejemplo: no me importa recordar las normas DIN / ISO exactas que contienen las reglas sobre cómo y dónde se debe colocar el cableado eléctrico en una casa privada, solo el significado / intención de las reglas, pero no el texto literal.
    Esto también tiene serias desventajas. ¿Cómo puede ser que tenga que resolver el mismo problema dos veces porque olvidé cómo lo resolví la primera vez, oa veces no puedo explicar de inmediato por qué hice algo de una manera específica, pero soy un poco bueno en eso? .

    Nunca pensé mucho en esto sobre los pros y los contras de aprender a estacionar y es más interesante de lo que esperaba (lea inglés y alemán).

    ¿Se siguen enseñando las tablas de multiplicar en los Estados Unidos? ¿Solo algunos estados? ¿Solo algunos formularios escolares?
    No pude encontrar respuestas útiles / definitivas sobre esto para Alemania o los Estados Unidos.

    Cuando lo recuerda y lo usa, ¿cómo funciona exactamente el proceso de pensamiento? p.ej. para 7 × 8 y 13 × 17?

    Algunos enlaces interesantes o "aterradores":
    https://www.nytimes.com/2014/07/27/magazine/why-do-americans-stink-at-math.html
    https://www.quora.com/Should-children-memorize-the-multiplication-tables-If-yes-what-is-the-upper-limit

    • J. Samson dice:

      Tanta arrogancia ...

      • Un hombre viejo dice:

        Parece ser miembro del think tank "nunca memorizar, multiplicar infinitas veces". ¡No querría gastar esa "habilidad"! SMGDMFCSH.

        Escúchame ahora y créeme después: la tabla de multiplicar ES una tabla de búsqueda (LUT para los niños fríos).

        • Greenaum dice:

          Estoy seguro de que incluso una adición se hace memorizando. Lo practicas mucho de niño. ¿Ha desarrollado el cerebro humano una instalación matemática discreta precisa cuando todo lo demás es un atajo para sacar rápidamente conclusiones aproximadas?

          Recuerda cuántos son cada par de números. No los cuentas, ¿verdad? No haces XOR y AND como lo haría una computadora.

          Para la multiplicación, recuerdo todos los cuadrados y algunos otros resultados, luego ajusto sumando o restando según sea necesario. A lo largo de los años, más niños se han quedado allí.

          No recuerdo haberlos aprendido de memoria en la escuela, y si lo hice, los olvidé como sospecho que todos hicieron. Entonces recuerda parcialmente a algunos y reconstruye otros. La mayoría de las personas son bastante malas en matemáticas, por lo que memorizar el aprendizaje, cantar al unísono, que es siete o nueve, no parece funcionar.

          • Un hombre viejo dice:

            Se garantiza que un método no utilizado no funcionará.

  • Comedias dice:

    Se perdió la base de la búsqueda de que sus datos se utilizan como la dirección del resultado deseado. La construcción de una mesa así es la "cocción". Soy un entusiasta serio de la búsqueda de trucos. En procesadores con E / S de fácil asignación de memoria, como el 6502, se pueden incrustar tablas de búsqueda grandes en unos pocos bytes de RAM y puede acelerar incluso operaciones simples en un factor de 10 (o más).

    Por ejemplo, para verificar que un carácter ASCII representa un número del 0 al 9. El 6502 puede leer o escribir en los primeros 256 bytes de RAM (cero) en 3 ciclos. EPROM / ROM se puede asignar a un solo byte de RAM en Zero Page. Los primeros 256 bytes de ROM se cargan con todos los FF hexadecimales excepto las ubicaciones 48 a 57, que tienen 00. Para usar, escriba un carácter ASCII en la entrada asignada a ROM, donde se usa como dirección. Lea el mismo lugar para obtener el contenido de la tabla, que será nulo si el carácter es un número.

    Pero ve al siguiente paso. Llene la ROM con FF hexadecimal, excepto los lugares 40 a 57, donde coloca el valor binario de los números del 0 al 9. Ahora, las operaciones de escritura / lectura individuales devuelven FF si el ASCII no es un número y el valor binario correcto si lo es. Esto toma seis ciclos y solo 4 bytes de código. El método de codificación habitual toma un par de comparaciones y ramificaciones con una resta o cambio que dura de 50 a 100 ciclos. El método LUT es 10 veces más rápido o más.

    Puede aplicar esto a un montón de fragmentos, como la multiplicación instantánea de 8 bits. O con las EEPROMS muy grandes de hoy, multiplicación instantánea de 16 bits. Con pequeñas micro-ROM, las ROM utilizadas pueden minimizar el espacio de código requerido y dar una velocidad notable. Se pueden combinar muchos LUTS en una ROM con esquemas de direcciones creativos.

    Además, las rutinas LUT son tan cortas que solo pueden funcionar en línea en lugar de tener un rendimiento inferior.

    Lo siento si repito, pero aún no pude ver toda la actuación. Hice todo esto en la década de 1980 con 6502 en instrumentos científicos. Con procesadores de 1 MHz, la ganancia fue asombrosa. (Ahora necesito mirar el lenguaje ensamblador AVR328 para buscar trucos divertidos con Arduino).

    • mia2c dice:

      - Solo quería decir que su comentario fue apreciado y muy interesante.

    • cnlohr dice:

      Ooohh, eso es realmente bueno. Intentaré recordarlo para el futuro. Lo uso MUCHO en MUCHOS proyectos, ¡y te dejo “doblar” la tabla de búsqueda en un tamaño mucho más pequeño! Lo uso para lidiar con la lógica de NTSC diciendo "lo que hace la línea" en cualquier caso, luego otra LUT realmente hace la salida.

  • Rick Bryan dice:

    El IBM 1620 no podía multiplicar de forma nativa, por lo que cualquier programa que requiriera multiplicación tenía que cargar una tabla de multiplicar LUT de memoria baja. (No vi el discurso, lo siento si ya te lo dijo).

    • js dice:

      Tampoco se podía sumar ni restar; toda su ALU se implementó como una tabla de búsqueda.

  • Rupin dice:

    Me preguntaba si LUT se puede utilizar para evaluar hashes en criptomonedas. Básicamente, ¿qué hace un minero?

    • Erik Johnson dice:

      ¿Como una mesa de arcoíris?

    • Greenaum dice:

      En teoría, puede usar LUT para absolutamente cualquier cosa. La principal desventaja es que crecen muy rápidamente. Es decir, por cada bit adicional en la entrada que desee calcular, debe duplicar el tamaño de la tabla. Una matriz para buscar 8 bits de material es de 256 bytes. Para 16 bits (digamos, multiplique 2 números de 8 bits, o haga algo con 2 números de 8 bits) tendría una longitud de 64K. Para 32 bits sería 4GB y para mucho más, prácticamente enorme. ¿Qué tan grande es el hachís?

      Las LUT son un problema bien conocido incluso para un programador novato. Dado que la minería de monedas es un millón de dólares (¿cuál es el valor de los Bitcoins actualmente existentes al precio actual?), Sospecho que si eso sería revolucionario, o incluso daría una ventaja del 5%, ya lo estarían haciendo. Los desarrolladores muy inteligentes entienden el tipo de cosas criptográficas en las que se basa Bitcoin. Similar You-Know-Who rompió una gran cantidad de cifrado, o lo intentó. Saben acerca de las LUT.

      Observo que esto no responde directamente a su pregunta, pero al menos puedo decirle si es bueno que ya lo hagan, y tal vez bien. ¡No ganarás millones así!

      • Greenaum dice:

        Está bien, lo estaba buscando. Los hacks de Bitcoin tienen una longitud de 64, 128 o 256 bits. Para una tabla de búsqueda de 64 bits, necesitaría 17179869184 gigabytes de almacenamiento, aunque podría buscarlo en una fracción de segundo. ¿El espacio de almacenamiento que necesitaría (alguien está buscando cuánto almacenamiento en la nube hay en el mundo) costaría menos que las monedas que podría crear? Pero ese es solo el más pequeño de 64 bits.

        En el futuro, por supuesto, el almacenamiento y la memoria aumentarán. Hasta que dieron el golpe, como hicieron las CPU con la Ley de Moore. Pero me dijeron que Bitcoin descubrió dónde es difícil crear cada moneda, Satoshi lo pensó. Lo cual es bueno, porque la moneda global expuesta que se está derritiendo debido a que los discos duros ha aumentado no serviría de mucho. Así que la respuesta es definitivamente "no". Es algo en el que tendrías que empezar a usar todos los átomos de un planeta para almacenar tu mesa.

      • Greenaum dice:

        Lamento publicar dos veces, pero acabo de notar que primero tendrás que contar todos los valores hash para mantenerlos en la tabla. Entonces, asumiendo que lo haces con los valores de 128 y 256 bits, y logras acceder a universos adicionales para almacenar los datos, llenando la tabla de que habrías extraído cada bitcoin de todos modos. En el momento en que lo completara, sería el momento en que se volvería obsoleto.

        Estoy un poco enojado porque recuerdo el comienzo de bitcoin, casi cuando la gente compraba tarjetas gráficas, con bitcoin, a mi más bitcoin. Las personas que vendieron las tarjetas gráficas deberían estar felices ahora. En ese momento pensé que eran un poco estúpidos y no les importaba la minería, ya que la cosa parecía una pérdida de tiempo un poco loca por parte de algunos desarrolladores de computadoras libertarios (ambos a menudo similares por razones que no quiero hacer) entran ) eso nunca significaría nada. Apuesto a que a muchos de los primeros mineros se les cobra absolutamente todo si retenían las monedas hasta que subiera el valor.

        Eso sí, probablemente explotaría una mina de drogas 5 minutos después de que se abriera Silk Road contra $ 5 bitcoins. Entonces no importa.

  • fpgcomputadora dice:

    Estoy buscando una mesa para mi espectro de sonido para algunos de mis proyectos. Calcula 20 * log10 (sqrt ()) para las sumas de cuadrados silenciosos de FFT. es decir, tamaño complejo a dB UV + escalado y trazado de píxeles tal como el código realiza una búsqueda lineal.

    ¿Por qué preocuparse por deslizar las funciones log10 y sqrt cuando solo necesito un resultado int8 distintivo bajo?

    • Bill Stewart dice:

      Para Square Roots, un método aún más rápido que una tabla de búsqueda es "simplemente no ejecutarlos"; El libro Pearl Programming de Jon Bentley habla sobre cuánto tiempo calcula sqrt (a ** 2 * b ** 2), lo comparará con otros valores calculados de la misma manera (por ejemplo, encuentre el par de puntos con la distancia más corta entre ellos), así que simplemente haga las comparaciones con el valor del cuadrado, y luego, si luego necesita obtener la distancia real, puede calcularla solo una vez en lugar de cada par de puntos.

  • CoM dice:

    Recuerdo esos pequeños conectores rápidos de mi infancia, estaban en el tren Lionel en casa de mi abuela. ¿Cómo se llaman?

  • Harvie.CZ dice:

    Me pregunto si puedo usar LUT en ESP32 a señales RF bitbang-433MHz para controlar esos interruptores alternos baratos ...

    • Greenaum dice:

      ¡Charles Lohr podría! Mira las locuras que ha hecho aquí para demostrarlo. Mi favorito fue la transmisión de software de video RF NTSC modulado.

  • lógica combinada dice:

    También una muy buena explicación sobre cómo abordar el primer paso de Newton-Raphson en un algoritmo de diapositiva dividida usando una tabla de búsqueda: http://www.acsel-lab.com/arithmetic/arith9/papers/ARITH9_Fowler.pdf

Alejandro Vargas
Alejandro Vargas

Deja una respuesta

Tu dirección de correo electrónico no será publicada.