Float division by constant integer

Patent metadata

Field	Value
Publication number	US-11954456-B2
Application number	US-202318140571-A
Country	US
Kind code	B2
Filing date	Apr 27, 2023
Priority date	Aug 22, 2018
Publication date	Apr 9, 2024
Grant date	Apr 9, 2024

Abstract

A binary logic circuit for determining the ratio x/d where x is a variable integer input, the binary logic circuit comprising: a logarithmic tree of modulo units each configured to calculate x[a: b]mod d for respective block positions a and b in x where b>a with the numbering of block positions increasing from the most significant bit of x up to the least significant bit of x, the modulo units being arranged such that a subset of M−1 modulo units of the logarithmic tree provide x[0: m]mod d for all m∈{1, M}, and, on the basis that any given modulo unit introduces a delay of 1: all of the modulo units are arranged in the logarithmic tree within a delay envelope of [log 2 M]; and more than M−2 u of the subset of modulo units are arranged at the maximal delay of [log 2 M], where 2 u is the power of 2 immediately smaller than M.

First claim

What is claimed is:

1. A binary logic circuit for determining the ratio x/d where x is a variable integer input of w bits comprising M>8 blocks of bit width r≥1 bit, and d>2 is a fixed integer, the binary logic circuit comprising:
a logarithmic tree of modulo units each configured to calculate x[a: b]mod d for respective block positions a and b in x where b>a with the numbering of block positions increasing from the most significant bit of x up to the least significant bit of x, the modulo units being arranged such that a subset of M−1 modulo units of the logarithmic tree provide x[0:m]mod d for all m∈{1, M−1}, and, on the basis that any given modulo unit introduces a delay of 1, all of the modulo units are arranged in the logarithmic tree within a delay envelope of [log 2 M]; and
output logic configured to combine the outputs provided by the subset of M−1 modulo units with blocks of the input x so as to yield the ratio x/d;

wherein the total number of modulo units T in the logarithmic tree for a given number of blocks M is in accordance with the following table:

M
T

24
46

25
48

26
51

27
54

28
58

29
61

30
65

31
69

32
74

33
60

34
62

35
64

36
67

37
69

38
72

39
74

40
78

41
80

42
83

43
85

44
89

45
91

46
94

47
96

48
101

49
103

50
106

51
109

52
113

53
116

54
120

55
123

56
128

57
131

58
135

59
139

60
144

61
148

62
153

63
158

64
164

65
133

66
135

67
137

68
140

69
142

70
145

71
147

72
151

73
153

74
156

75
158

76
162

77
164

78
167

79
169

80
174

81
176

82
179

83
181

84
185

85
187

86
190

87
192

88
197

89
199

90
202

91
206

92
210

93
214

94
217

95
219

96
225

97
227

98

Assignees

• Imagination Tech Ltd

Inventors

• Kallen Jonas
• Elliott Sam

Classifications

• G06F7/556 Primary

  Logarithmic or exponential functions · CPC title

• G06F7/4873

  Dividing · CPC title

• G06F7/727 Primary

  Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence) · CPC title

• G06F7/535 Primary

  Dividing only · CPC title

• G06F7/483

  Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)} · CPC title