Algorithms to compute the class number
Let the class number $h(d)$ denote the number of distinct binary quadratic forms with discriminant $d < 0$.
Is there a better algorithm for $h$ than brute force?
To be precise, by brute force I meant to generate enough forms to completely cover the space and then reducing them down to see how many equivalence classes there are.
Yes, there are algorithms that are much better than brute force. For example, see section 5.4 in Henri Cohen's book "A course in computational algebraic number theory" for Shanks's baby-step giant-step algorithm $O(|D|^{1/4+\epsilon})$ - which is practical for negative discriminants $D$ up to 25 digits or more and, further, McCurley's sub-exponential algorithm (including Atkin's variant) which is $O(L(|D|)^\alpha)$ for $\alpha = \sqrt 2 \;$ or perhaps even $\alpha = \sqrt{9/8},$ where $\; L(x) = e^{\sqrt {\ln x \ln\ln x}}$. This can handle $D$ up to 50 digits or more (nowadays, with various improvements, probably around 80 digits or more - the prior numbers are quoted from the 1993 edition of Cohen's book - currently the bible for computational algebraic number theory).
We use the notation of this question. Let $D$ be a negative non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Let $\Gamma = SL_2(\mathbb{Z})$. We denote the set of positive definite primitive binary quadratic forms of discriminant $D$ by $\mathfrak{F}^+_0(D)$. By this question, $\mathfrak{F}^+_0(D)$ is $\Gamma$-invariant. We denote the set of $\Gamma$-orbits on $\mathfrak{F}^+_0(D)$ by $\mathfrak{F}^+_0(D)/\Gamma$. Let $h(D) = |\mathfrak{F}^+_0(D)/\Gamma|$.
Let $\mathcal{H} = \{z \in \mathbb{C}; Im(z) > 0\}$. We denote by $\mathcal{H}(D)$ the set of quadratic numbers of discriminant $D$ in $\mathcal{H}$. By this question, $\mathcal{H}(D)$ is $\Gamma$-invariant. We denote the set of $\Gamma$-orbits on $\mathcal{H}(D)$ by $\mathcal{H}(D)/\Gamma$.
Let $f = ax^2 + bxy + cy^2 \in \mathfrak{F}^+_0(D)$. We denote $\phi(f) = (-b + \sqrt{D})/2a$, where $\sqrt{D} = i\sqrt{|D|}$. It is clear that $\phi(f) \in \mathcal{H}(D)$. Hence we get a map $\phi\colon \mathfrak{F}^+_0(D) \rightarrow \mathcal{H}(D)$. By this question, $\phi$ is a bijection and induces a bijection $\mathfrak{F}^+_0(D)/\Gamma \rightarrow \mathcal{H}(D)/\Gamma$. Hence, computing $h(D)$ is the same as computing $|\mathcal{H}(D)/\Gamma|$.
Let $G = \{ z \in \mathcal{H}\ |\ -1/2 \le Re(z) \lt 1/2, |z| \gt 1$ or $|z| = 1$ and $Re(z) \le 0 \}$. It is known that $G$ is a fundamental domain of $\mathcal{H}/\Gamma$(e.g. Serre's A Course in Arithmetic).
Hence it suffices to count the number of $f \in \mathfrak{F}^+_0(D)$ such that $\phi(f) \in G$. Let $f = ax^2 + bxy + cy^2$. Then $\phi(f) \in G$ if and only if $|b| \le a \le c$(if $|b| = a$ or $a = c, b \ge 0)$. Hence it suffices to count the number of $(a, b, c)$ which satisfies the following conditions.
- $a \gt 0$.
- gcd$(a, b, c) = 1$.
- $D = b^2 - 4ac$.
- $|b| \le a \le c$, if $|b| = a$ or $a = c, b \ge 0$.
The following observation suffices to determine $(a, b, c)$.
Since $D = b^2 - 4ac, 4ac = b^2 + |D|$. Hence $c = (b^2 + |D|)/4a$. Hence it suffices to determine $a$ and $b$.
Since $a \le c$, $a \le (b^2 + |D|)/4a$. Hence $4a^2 \le b^2 + |D| \le a^2 + |D|$. Hence $3a^2 \le |D|$. Hence $a^2 \le |D|/3$. Hence $a \le \sqrt{|D|/3}$.
As an example, we compute $h(D)$ when $D = -584 = -2^3\cdot73$ by our method. This is the class number of $\mathbb{Q}(\sqrt {-146})$.
$a \le \sqrt{|D|/3} = \sqrt{\frac{584}{3}} = 13.95\cdots$. Hence $1 \le a \le 13$.
$4ac = b^2 + |D| = b^2 + 584$. Hence $b^2 \equiv 0$ (mod $2$). Hence $b$ is even. We compute $b^2 + 584$ for $0 \le b \le 13$.
$0^2 + 584 = 584 = 4\cdot146 = 4\cdot2\cdot73$
$2^2 + 584 = 588 = 4\cdot147 = 4\cdot3\cdot7^2$
$4^2 + 584 = 600 = 4\cdot150 = 4\cdot2\cdot3\cdot5^2$
$6^2 + 584 = 620 = 4\cdot155 = 4\cdot5\cdot31$
$8^2 + 584 = 648 = 4\cdot162 = 4\cdot2\cdot3^4$
$10^2 + 584 = 684 = 4\cdot171 = 4\cdot3^2\cdot19$
$12^2 + 584 = 728 = 4\cdot182 = 4\cdot2\cdot7\cdot13$
Thus we get the following results.
$a = 1\colon\ |b| = 0, c = 2\cdot73 = 146, (a, b, c) = (1, 0, 146)$
$a = 2\colon\ |b| = 0,c = 73, (a, b, c) = (2, 0, 73)$
$a = 3\colon\ |b| = 2,c = 7^2 = 49,(a, b, c) = (3, \pm2, 49)$
$a = 4\colon$ none
$a = 5\colon\ |b| = 4,c = 2\cdot3\cdot5 = 30,(a, b, c) = (5, \pm4, 30)$
$a = 6\colon\ |b| = 4,c = 5^2 = 25,(a, b, c) = (6, \pm4, 25)$
$a = 7\colon\ |b| = 2,c = 3\cdot7 = 21,(a, b, c) = (7, \pm2, 21)$
$a = 8 \colon$ none
$a = 9 \colon\ |b| = 8,c = 2\cdot3^2 = 18,(a, b, c) = (9, \pm8, 18)$
$a = 10 \colon\ |b| = 4,c = 3\cdot5 = 15,(a, b, c) = (10, \pm4, 15)$
$a = 11\colon$ none
$a = 12\colon$ none
$a = 13\colon\ |b| = 12,c = 2\cdot7 = 14,(a,b,c) = (13, \pm12, 14)$
Therefore $h(D) = 16$.