32-Digit Hexadecimal Vertical Ladner-Fischer Adder in Minecraft

Overview

This Minecraft implementation is a 32-digit hexadecimal Ladner-Fischer Adder (LFA), a type of Parallel Prefix Adder (PPA) that balances the speed of carry-lookahead adders with the simplicity of ripple-carry adders. It's designed for high-performance addition operations within the constraints of Minecraft's redstone system.

Key Features

• Vertical design utilizing Minecraft's signal propagation
• Processes 128 binary bits (32 hexadecimal digits) in parallel
• Torchless implementation for Minecraft efficiency
• Synchronized operation at 5Hz regardless of input
• Pure Ladner-Fischer architecture optimized for Minecraft

Understanding the Ladner-Fischer Structure

The LFA consists of four main stages, labeled S1 through S4:

1. S1 (Stage 1): This is the preprocessing stage. Each S1 block takes two input bits and computes initial propagate (P) and generate (G) signals.
2. S2 (Stage 2): Combines results from pairs of S1 blocks, calculating group P and G signals for 4-bit groups.
3. S3 (Stage 3): Further combines results from S2, handling 8-bit groups.
4. S4 (Stage 4): The final stage, which calculates the carry for the entire 16-bit section.

How to interpret the structure:

• Signals flow from top (inputs) to bottom (outputs).
• Each stage combines information from the previous stage, allowing parallel computation of carries.
• Lower-order bits are resolved earlier, while higher-order bits utilize more stages.

Performance

The implementation leverages the logarithmic depth of LFA (O(log n)):

• Consistent 5Hz operation for all inputs, regardless of complexity
• Significantly outperforms Ripple Carry Adders (RCA) for large numbers

This graph illustrates the time complexity of different adder types:

• RCA (Ripple Carry Adder): Shows linear growth O(n/2), becoming increasingly slower as bit count increases.
• PPA (Parallel Prefix Adder, including LFA): Demonstrates logarithmic growth O(log n), more efficient for larger bit counts.
• CCA (Carry Cancel Adder): Shown for comparison, exhibits stepwise linear growth, very efficient for smaller bit counts.

The vertical dashed line at 32 bits (8 hex digits) shows where this implementation operates, demonstrating its efficiency compared to RCA and its practical performance in the Minecraft environment.

Visual Representation

These diagrams illustrate the Ladner-Fischer structure:

• Pink boxes at the top represent inputs (0-15 for a 16-bit section)
• Gray boxes (S1, S2, S3, S4) show the four computation stages
• Bottom gray boxes represent outputs, aligned with their corresponding inputs

The structure demonstrates how carry information propagates efficiently through the adder, allowing for fast, parallel computation even with large numbers.